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.

Link to Full Text

Share

COinS