Premium
k ‐Factors and Neighbourhoods of Independent Sets in Graphs
Author(s) -
Woodall D. R.
Publication year - 1990
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-41.3.385
Subject(s) - combinatorics , mathematics , statement (logic) , graph , discrete mathematics , law , political science
Sufficient conditions are proved for the existence of a k ‐factor or a Hamiltonian circuit in a graph G . The main element of each condition is a statement to the effect that | N ( X )| ⩾ a | X | + b | V ( G )| + c for every non‐empty independent subset X of V ( G ). The theorems are shown to contain various known results.