# On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

## Keywords:

Digraphs, Cycles, Hamiltonian cycles, Hamiltonian bypasses## Abstract

Let D be a strongly connected directed graph of order n ≥ 4 which satisfies the following condition (*): for every pair of non-adjacent vertices x, y with a common in-neighbour d(x) + d(y) ≥ 2n - 1 and min {d(x), d(y)} ≥ n - 1. In [2] (J. of Graph Theory 22 (2) (1996) 181-187)) J. Bang-Jensen, G. Gutin and H. Li proved that D is Hamiltonian. In [9] it was shown that if D satisfies the condition (*) and the minimum semi-degree of D at least two, then either D contains a pre-Hamiltonian cycle (i.e., a cycle of length n - 1) or n is even and D is isomorphic to complete bipartite digraph (or to complete bipartite digraph minus one arc) with equal partite sets. In this paper we show that if the minimum out-degree of D at least two and the minimum in-degree of D at least three, then D contains also a Hamiltonian bypass, (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc).

## References

J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000.

J. Bang-Jensen, G. Gutin, H. Li, “Sufficient conditions for a digraph to be Hamiltonian", Journal of Graph Theory, vol. 22 no. 2, pp. 181-187, 1996.

J. Bang-Jensen, Y. Guo, A.Yeo, “A new sufficient condition for a digraph to be Hamiltonian", Discrete Applied Mathematics, vol. 95, pp. 77-87, 1999.

A.Benhocine, “On the existence of a specified cycles in digraphs with constraints on degrees", Journal of Graph Theory, vol. 8, pp.101 -107, 1984.

J.A. Bondy, C. Thomassen, “A short proof of Meyniel's theorem", Discrete Mathematics, vol. 19, no. 1, pp. 85-92, 1977.

S.Kh. Darbinyan, "A sufficient condition for the Hamiltonian property of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Doklady, (see also arXiv: 1111.1843v1 [math.CO] 8 Nov 2011), vol. 82, no. 1, pp.6-8, 1986.

S.Kh. D arbinyan, “On Hamiltonian bypasses in digraphs satisfying Meyniel-like conditions", Mathematical Problems in Computer Science, (see also Proceedings of 5-th science-technical conference for yang researchers, p. 23, Tsaghkadzor, Armenia, 1986), ( in Russian), vol. 20, pp.7-19, 1998.

S.Kh. Darbinyan, “On the specified cycles in oriented graphs", Akademy Nauk Armyan. SSR Doklady, (in Russian), vol. 84, no. 1, pp. 51-55, 1987.

S.Kh. Darbinyan, I. A. Karapetyan, “On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li", Preprint available at htte: arXiv 1207.5643v2 [math.CO], 20 Sep 2012.

S.Kh. Darbinyan, I. A. Karapetyan, “A note on long non-Hamiltonian cycles in one class of digraphs", P reprint available at htte: arXiv 1209.4456v1 [math.CO], 20 Sep 2012.

R. Häggkvist, C. Thomassen, “On pancyclic digraphs", Journal Combinatorial Theory Ser. B, vol. 20, pp. 20-40, 1976.

A. Ghouila-Houri, “Une condition suffisante d'existence d'un circuit hamiltonien", Comptes Rendus de I'Academie des Sciences Paris Ser. A-B, no. 251, pp. 495-497, 1960.

M. Meyniel, “Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente", Journal Combinatorial Theory Ser. B, vol. 14, pp. 137-147, 1973.

C.St.J.A. Nash-Williams, “Hamilton circuits in graphs and digraphsit. The many facts of graph theory", Springer Lecture Notes. 110, pp.237-243, 1969.

C. Thomassen, “Long cycles in digraphs", Proceeding London Mathematical Society, vol. 3, no. 42, pp. 231-251, 1981.

D. R. Woodall, “Sufficient conditions for circuits in graphs", Proceeding London Mathematical Society, no. 24, pp. 739-755, 1972.

## Downloads

## Published

## How to Cite

*Mathematical Problems of Computer Science*,

*41*, 23–37. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/226

## Issue

## Section

## License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.