Premium
On the number of ( r,r +1)‐ factors in an ( r,r +1)‐factorization of a simple graph
Author(s) -
Hilton A. J. W.
Publication year - 2009
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.20356
Subject(s) - combinatorics , mathematics , graph , simple graph , factorization , integer (computer science) , discrete mathematics , disjoint sets , computer science , algorithm , programming language
For integers d ≥0, s ≥0, a ( d, d + s )‐ graph is a graph in which the degrees of all the vertices lie in the set { d, d +1, …, d + s }. For an integer r ≥0, an ( r, r +1)‐ factor of a graph G is a spanning ( r, r +1)‐subgraph of G . An ( r, r +1)‐ factorization of a graph G is the expression of G as the edge‐disjoint union of ( r, r +1)‐factors. For integers r, s ≥0, t ≥1, let f ( r, s, t ) be the smallest integer such that, for each integer d ≥ f ( r, s, t ), each simple ( d, d + s ) ‐graph has an ( r, r +1) ‐factorization with x ( r, r +1) ‐factors for at least t different values of x . In this note we evaluate f ( r, s, t ). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009