A characterization by forbidden induced subgraphs of those graphs whose probe graphs are weakly chordal
David Chandler
University of Delaware

Abstract:

A probe graph is obtained from a graph by selecting certain vertices as probes and then deleting any edge that does not have at least one probe endvertex. A weakly chordal graph is one which does not have any holes or antiholes as induced subgraphs. A hole is a chordless cycle of length at least five, and an antihole is the complement of a hole. We show that the family of graphs whose probe graphs are necessarily weakly chordal is precisely those graphs with no induced hole, house, domino, nor sun.

Joint work with Ton Kloks, Maw-Shang Chang, and Sheng-Lung Peng