Premium
Edge disjoint cycles in graphs
Author(s) -
Hao Li
Publication year - 1989
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.3190130306
Subject(s) - combinatorics , mathematics , disjoint sets , hamiltonian path , graph , pancyclic graph , hamiltonian (control theory) , discrete mathematics , line graph , 1 planar graph , mathematical optimization
Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n , then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ⩾ 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ⩾ 2δ 2 , then for any 3 ⩽ l 1 ⩽ l 2 ⩽ ⃛ ⩽ l k ⩽ n , 1 = k = [(δ ‐ 1)/2], such graph has K edge disjoint cycles with lengths l 1 , l 2 …l k , respectively. In particular, when l 1 = l 2 = ⃛ = l k = n and k = [(δ ‐ 1)/2], the graph contains [(δ ‐ 1)/2] edge disjoint hamiltonian cycles.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom