A Note on Hamiltonian Bypasses in Digraphs with Large Degrees

Authors

  • Samvel Kh. Darbinyan Institute for Informatics and Automation Problems of NAS RA

DOI:

https://doi.org/10.51408/1963-0055

Keywords:

Digraph, cycle, Hamiltonian cycle, Hamiltonian bypass

Abstract

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

2021-12-10

How to Cite

Darbinyan, S. K. . (2021). A Note on Hamiltonian Bypasses in Digraphs with Large Degrees. Mathematical Problems of Computer Science, 54, 7–17. https://doi.org/10.51408/1963-0055