Structural characterization and efficient recognition of probe diamond-free graphs

Luciano Norberto Grippo Min Chih Lin

A graph is probe diamond-free if its vertex set admits a partition into probes and nonprobes, where the set of nonprobes is independent, such that adding edges only between pairs o…