Contents

-

Dual-Chordal and Strongly Dual-Chordal Graphs

Terry A. McKee1
1Department of Mathematics & Statistics Wright State University, Dayton, Ohio 45435 USA

Abstract

A graph is chordal if and only if every cycle either has a chord or is a triangle. If an edge (or triangle) is defined to be a strength-k edge (or triangle) whenever it is in at least k maximum cliques, then a graph is strongly chordal if and only if, for every k1, every cycle of strength-k edges either has a strength-k chord or is a strength-k triangle. Dual-chordal graphs have been defined so as to be the natural cycle/cutset duals of chordal graphs. A carefully crafted notion of dual strength allows a characterization of strongly dual-chordal graphs that is parallel to the above. This leads to a complete list of all 3-connected strongly dual-chordal graphs.