Premium
Rao's conjecture on self‐complementary graphs with K ‐factors
Author(s) -
Ando Kiyoshi
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090109
Subject(s) - counterexample , conjecture , mathematics , combinatorics , graph , degree (music) , order (exchange) , discrete mathematics , physics , finance , acoustics , economics
Rao posed the following conjecture, “Let G be a self‐complementary graph of order p , π = (d 1 … dp) be its degree sequence. Then G has a k‐factor if and only if π − k, = (d1 − k, … dP − k) is graphical.” We construct a family of counterexamples for this conjecture for every k ⩾ 3.