#### Title

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