On Circular Critical Graphs
Document Type
Article
Publication Date
1984
Published In
Discrete Mathematics
Abstract
A graph on n vertices is called circular if its automorphism group contains an n-cycle. Let ω(G) and α(G) be, respectively, the clique number and the independence number of the graph G. A graph G with n vertices is called an (α, ω)-graph if 1. (1) n=α(G)ω(G)+1 2. (2) every vertex is in exactly α(G) maximum independent sets and α(G) maximum cliques, and 3. (3) each maximum clique intersects all but one maximum independent set, and vice versa. A graph is called critical if it is imperfect and all of its proper induced subgraphs are perfect. Lovasz and Padberg showed that all critical graphs are (α, ω)-graphs. Only one method is known for constructing circular (α, ω)-graphs. We show that the only critical graphs which arise from this construction are the odd, chordless cycles of length at least 5, and their complements.
Recommended Citation
Charles M. Grinstead.
(1984).
"On Circular Critical Graphs".
Discrete Mathematics.
Volume 51,
Issue 1.
11-24.
DOI: 10.1016/0012-365X(84)90019-0
https://works.swarthmore.edu/fac-math-stat/58
