DIMACS TR: 2009-10

A Characterization of Almost CIS Graphs



Authors: Yezhou Wu, Wenan Zang and Cun-Quan Zhang

ABSTRACT

A graph G is called CIS if each maximal clique intersects each maximal stable set in G, and is called almost CIS if it has a unique disjoint pair (C; S) consisting of a maximal clique C and a maximal stable set S. While it is still unknown if there exists a good structural characterization of all CIS graphs, in this note we prove the following Andrade-Boros-Gurvich conjecture: A graph is almost CIS if and only if it is a split graph with a unique split partition.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-10.pdf
DIMACS Home Page