On graphs whose maximal cliques and stable sets intersect
D. V. Andrade, E. Boros, and V. Gurvich
RUTCOR Research Report 17-2006, Rutgers University, 2006.

Abstract: We say that a graph G has the CIS-property and call it a CIS-graph if every maximal clique and every maximal stable set of G intersect. By definition, G is a CIS-graph if and only if the complementary graph G is a CIS-graph. Let us substitute a vertex v of a graph G' by a graph G'' and denote the obtained graph by G. It is also easy to see that G is a CIS-graph if and only if both G' and G'' are CIS-graphs. In other words, CIS-graphs respect complementation and substitution. Yet, this class is not hereditary, that is, an induced subgraph of a CIS-graph may have no CIS-property. Perhaps, for this reason, the problems of efficient characterization and recognition of CIS-graphs are difficult and remain open. In this paper we only give some necessary and some sufficient conditions for the CIS-property to hold.

[full text pdf]

Last Updated on February 9, 2007