A Note on Hamiltonian Bypasses in Digraphs with Large Degrees
DOI:
https://doi.org/10.51408/1963-0055Keywords:
Digraph, cycle, Hamiltonian cycle, Hamiltonian bypassAbstract
Let D be a 2-strongly connected directed graph of order p ≥ 3. Suppose that d(x) ≥ p for every vertex x ∈ V (D) \ {x0}, where x0 is a vertex of D. In this paper, we show that if D is Hamiltonian or d(x0) > 2(p − 1)/5, then D contains a Hamiltonian path, in which the initial vertex dominates the terminal vertex.
References
J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2001.
J.-C. Bermond and C. Thomassen, “Cycles in Digraphs-A Survey”, Journal of Graph Theory, vol. 5, pp. 1-43, 1981.
D. K¨uhn and D. Osthus, “A survey on Hamilton cycles in directed graphs”, European Journal of Combinatorics, vol. 33, pp. 750-766, 2012.
A. Benhocine and A.P. Wojda, “Bypasses in Digraphs”, Ars Combinatoria, vol. 16, pp. 85-94, 1983.
A. Benhocine, “On the existence of a specified cycle in digraphs with constraints on degrees”, Journal of Graph Theory, vol. 8, pp. 101-107, 1984.
S.Kh. Darbinyan, “On Hamiltonian bypasses in digraphs satisfying Meyniel-like condition”, Transactions of IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 20, pp. 7-19, 1998.
S.Kh. Darbinyan, “On the specified cycles in oriented graphs”, Akademy Nauk Armyan. SSR Dokllady, vol. 84, no. 2, pp. 51-55, 1987 (in Russian).
S.Kh. Darbinyan and I.A. Karapetyan, “On Hamiltonian bypasses in one class of Hamiltonian digraphs”, Mathematical Problems of Computer Science, vol. 41, pp. 23-37, 2014.
S.Kh. Darbinyan, “On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis”, ”2015 Computer Science and Information Technologies (CSIT), Yerevan, doi:10.1109/CSITechnol.2015.7358250, pp. 53-63, 2015.
S.Kh. Darbinyan, “On Hmiltonian and strongly Hamiltonconnected digraphs”, Akademy Nauk Armyan. SSR Doklady, vol. 91, no. 1, pp. 3-6, 1990.(arXiv.1801.05166v1).
S.Kh. Darbinyan, “A sufficient condition for a digraph to be Hamiltonian”, Akademy Nauk Armyan. SSR Doklady,(in Russian), vol. 91, no. 2, pp. 57-59, 1990.
R. H¨aggkvist and C. Thomassen, “On pancyclic digraphs”, Journal Combinatorial Theory ser. B, vol. 20, pp. 20-40, 1976.
J.A. Bondy and C. Thomassen, “A short proof of Meyniel’s theorem”, Discrete Mathematics, vol. 19, pp. 195-197, 1977.
J. Bang-Jensen, G. Gutin and H. Li, “Sufficient conditions for a digraph to be Hamiltonian”, Journal of Graph Theory, vol. 22, no. 2, pp. 181-187, 1996.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
