On CIS circulants

Endre Boros, Vladimir Gurvich, Martin Milanič

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

A circulant is a Cayley graph over a cyclic group. A well-covered graph is a graph in which all maximal stable sets are of the same size α=α(G), or in other words, they are all maximum. A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. It is not difficult to show that a circulant G is a CIS graph if and only if G and its complement Ḡ are both well-covered and the product α(G)α(Ḡ) is equal to the number of vertices. It is also easy to demonstrate that both families, the circulants and the CIS graphs, are closed with respect to the operations of taking the complement and the lexicographic product. We study the structure of the CIS circulants. It is well-known that all P4-free graphs are CIS. In this paper, in addition to the simple family of P4-free circulants, we construct a non-trivial sparse but infinite family of CIS circulants. We are not aware of any CIS circulant that could not be obtained from graphs in this family by the operations of taking the complement and the lexicographic product.

Original languageEnglish (US)
Pages (from-to)78-95
Number of pages18
JournalDiscrete Mathematics
Volume318
Issue number1
DOIs
StatePublished - Mar 6 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • CIS graph
  • Circulant
  • Maximal clique
  • Maximal stable set
  • Maximum clique
  • Maximum stable set
  • Well-covered graph

Fingerprint

Dive into the research topics of 'On CIS circulants'. Together they form a unique fingerprint.

Cite this