The number of pancyclic arcs contained in a Hamiltonian cycle of a tournament
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A tournament T is an orientation of a complete graph and an arc in T is called pancyclic if it is contained in a cycle of length l for all 3 ≤ l ≤ n, where n is the cardinality of the vertex set of T. In 1994, Moon [5] introduced the graph parameter h(T) as the maximum number of pancyclic arcs contained in the same Hamiltonian cycle of T and showed that h(T) ≥ 3 for all strong tournaments with n ≥ 3. Havet [4] later conjectured that h(T) ≥ 2k +1 for all k-strong tournaments and proved the case k = 2. In 2005, Yeo [7] gave the lower bound h(T)≥ k+5 2 for all k-strong tournaments T. In this note, we will improve his bound to h(T) ≥ 2k+7 3 .
Abstract
A tournament T is an orientation of a complete graph and an arc in T is called pancyclic if it is contained in a cycle of length l for all 3 ≤ l ≤ n, where n is the cardinality of the vertex set of T. In 1994, Moon [5] introduced the graph parameter h(T) as the maximum number of pancyclic arcs contained in the same Hamiltonian cycle of T and showed that h(T) ≥ 3 for all strong tournaments with n ≥ 3. Havet [4] later conjectured that h(T) ≥ 2k +1 for all k-strong tournaments and proved the case k = 2. In 2005, Yeo [7] gave the lower bound h(T)≥ k+5 2 for all k-strong tournaments T. In this note, we will improve his bound to h(T) ≥ 2k+7 3 .
참고문헌 (7)
- J. Bang-Jensen, "Digraphs: Theory" (2000), Algorithms and Applications
- P. Camion, "Chemins et circuits hamiltoniens des graphes complets", C. R. Acad. Sci. Paris, 249, pp.2151~2152 (1959)
- J. Feng, "Hamiltonian Cycles in Certain Graphs and Out-arc Pancyclic Vertices in Tour-naments", Ph.D, pp.2008
- F. Havet, "Pancyclic arcs and connectivity in tournaments", J. Graph Theory, 47(2), pp.87~110 (2004)
- J. W. Moon, "On k-cyclic and pancyclic arcs in strong tournaments", J. Combin. Inform. System Sci, 19(3-4), pp.207~214 (1994)
- C. Thomassen, "Hamiltonian-connected tournaments", J. Combin. Theory Ser. B, 28(2), pp.142~163 (1980)
- A. Yeo, "The number of pancyclic arcs in a k-strong tournament", J. Graph Theory, 50(3), pp.212~219 (2005)