Premium
On the structure of graphs with a unique k ‐factor
Author(s) -
Johann Petra
Publication year - 2000
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/1097-0118(200012)35:4<227::aid-jgt1>3.0.co;2-d
Subject(s) - combinatorics , mathematics , isomorphism (crystallography) , conjecture , graph isomorphism , graph , discrete mathematics , line graph , chemistry , crystal structure , crystallography
In this paper we study the structure of graphs with a unique k ‐factor. Our results imply a conjecture of Hendry on the maximal number m ( n,k ) of edges in a graph G of order n with a unique k ‐factor: For $k > {n\over 2}$ we prove $m(n,k)={nk\over 2} + \left({n- k\atop 2}\right)$ and construct all corresponding extremal graphs. For $k\le {n\over 2}$ we prove $m(n,k) \le {n^2\over 4} + (k - 1){n\over 4}$ . For n = 2 kl , l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000