Premium
Edge disjoint Hamilton cycles in graphs
Author(s) -
Li Guojun
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(200009)35:1<8::aid-jgt2>3.0.co;2-k
Subject(s) - combinatorics , mathematics , conjecture , disjoint sets , graph , integer (computer science) , discrete mathematics , computer science , programming language
Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2( k + 1)‐connected graph G , d G ( u , v ) = 2 implies that max{ d ( u ; G ), d ( v ; G )} ≥ ( n /2) + 2 k , then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000