Explore the vast range of titles available.

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: ıt Let$D$be a 2-strong digraph of order$n\\geq 9$ . If$n-1$vertices of$D$have degrees at least$n+k$and the remaining vertex has degree at least$n-k-4$ , where$k$is a non-negative integer, then$D$is Hamiltonian. This is an extension of Ghouila-Houri's theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for$k=0$there is a digraph of order$n=8$(respectively,$n=9$ ) with the minimum degree$n-4=4$(respectively, with the minimum$n-5=4$ ) whose$n-1$vertices have degrees at least$n-1$ , but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected.

Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. ıt Let$D$be a 2-strongly connected digraph of order$n$such that for all distinct pairs of non-adjacent vertices$x$ ,$y$and$w$ ,$z$ , we have$d(x)+d(y)+d(w)+d(z)\\geq 4n-3$ . Then$D$is Hamiltonian. In this paper, we confirm this conjecture. Moreover, we prove that if a digraph$D$satisfies the conditions of this conjecture and has a pair of non-adjacent vertices$\\{x,y\\}$such that$d(x)+d(y)\\leq 2n-4$ , then$D$contains cycles of all lengths$3, 4, \\ldots , n$ . Comment: 24 pages

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: {\\it Let \\(D\\) be a 2-strong digraph of order \\(n\\geq 9\\). If \\(n-1\\) vertices of \\(D\\) have degrees at least \\(n+k\\) and the remaining vertex has degree at least \\(n-k-4\\), where \\(k\\) is a non-negative integer, then \\(D\\) is Hamiltonian}. This is an extension of Ghouila-Houri's theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for \\(k=0\\) there is a digraph of order \\(n=8\\) (respectively, \\(n=9\\)) with the minimum degree \\(n-4=4\\) (respectively, with the minimum \\(n-5=4\\)) whose \\(n-1\\) vertices have degrees at least \\(n-1\\), but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected.

Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. \\noindent\\textbf{Conjecture}. {\\it Let \\(D\\) be a 2-strongly connected digraph of order \\(n\\) such that for all distinct pairs of non-adjacent vertices \\(x\\), \\(y\\) and \\(w\\), \\(z\\), we have \\(d(x)+d(y)+d(w)+d(z)\\geq 4n-3\\). Then \\(D\\) is Hamiltonian.} In this paper, we confirm this conjecture. Moreover, we prove that if a digraph \\(D\\) satisfies the conditions of this conjecture and has a pair of non-adjacent vertices \\(\\{x,y\\}\\) such that \\(d(x)+d(y)\\leq 2n-4\\), then \\(D\\) contains cycles of all lengths \\(3, 4, \\ldots , n\\).

Let \\(D\\) be a digraph of order \\(p5\\) with minimum degree at least \\(p-1\\) and with minimum semi-degree at least \\(p/2-1\\). In his excellent and renowned paper, ``Long Cycles in Digraphs\" (Proc. London Mathematical Society (3), 42 (1981), Thomassen fully characterized the following for \\(p=2n+1\\): (i) \\(D\\) has a cycle of length at least \\(2n\\); and (ii) \\(D\\) is Hamiltonian. Motivated by this result, and building on some of the ideas in Thomassen's paper, we investigated the Hamiltonicity (when \\(p\\) is even) and pancyclcity (when \\(p\\) is arbitrary) such digraphs. We have given a complete description of whether such digraphs are Hamiltonian (\\(p\\) is even), are pancyclic (\\(p\\) is arbitrary). Since the proof is very long, we have divided it into three parts. In this paper, we provide a full description of the following: (iii) for \\(k=3\\) and \\(k=4\\), the digraph \\(D\\) contains a cycle of length \\(k\\); and (iv) the digraph \\(D\\) contains a pre-Hamiltonian cycle, i.e. a cycle of length \\(p-1\\).

A Hamiltonian path in a digraph \\(D\\) in which the initial vertex dominates the terminal vertex is called a Hamiltonian bypass. Let \\(D\\) be a 2-strong digraph of order \\(p 3\\) and let \\(z\\) be some vertex of \\(D\\). Suppose that every vertex of \\(D\\) other than \\(z\\) has degree at least \\(p\\). We introduce and study a conjecture which claims that there exists a smallest integer \\(k\\) such that if \\(d(z) k\\), then \\(D\\) contains a Hamiltonian bypass. In this paper, we prove: (i) If \\(D\\) is Hamiltonian or \\(z\\) has a degree greater than \\((p-1)/3\\), then \\(D\\) contains a Hamiltonian bypass. (ii) If a strong balanced bipartite digraph \\(B\\) of order \\(2a 6\\) satisfies the condition that \\(d^+(u)+d^-(v) a+1\\) for all vertices \\(u\\) and \\(v\\) from different partite sets such that \\(B\\) does not contain the arc \\(uv\\), then \\(B\\) contains a Hamiltonian bypass. Furthermore, the lower bound \\(a+1\\) is sharp. The first result improves a result of Benhocine (J. of Graph Theory, 8, 1984) and a result of the author (Math. Problems of Computer Science, 54, 2020) We also suggest some conjectures and problems.

In this note we prove: ıt Let \\(D\\) be a 2-strong digraph of order \\(n\\) such that its \\(n-1\\) vertices have degrees at least \\(n+k\\) and the remaining vertex \\(z\\) has degree at least \\(n-k-4\\), where \\(k\\) is a positive integer. If \\(D\\) contains a cycle of length at least \\(n-k-2\\) passing through \\(z\\), then \\(D\\) is Hamiltonian.

Let \\(G\\) be a strongly connected directed graph of order \\(p 3\\). In this paper, we show that if \\(d(x)+d(y) 2p-2\\) (respectively, \\(d(x)+d(y) 2p-1\\)) for every pair of non-adjacent vertices \\(x, y\\), then \\(G\\) contains a Hamiltonian path (with only a few exceptional cases that can be clearly characterized) in which the initial vertex dominates the terminal vertex (respectively, \\(G\\) contains two distinct verteces \\(x\\) and \\(y\\) such that there are two internally disjoint \\((x,y)\\)-paths of lengths \\(p-2\\) and \\(2\\)).

C. Thomassen (Proc. London Math. Soc. (3) 42 (1981), 231-251) gave a characterization of strongly connected non-Hamiltonian digraphs of order \\(p\\geq 3\\) with minimum degree \\(p-1\\). In this paper we give an analogous characterization of strongly connected non-Hamiltonian digraphs with Meyniel-type condition (the sum of degrees of every pair of non-adjacent vertices \\(x\\) and \\(y\\) at least \\(2p-2\\)). Moreover, we prove that such digraphs \\(D\\) contain cycles of all lengths \\(k\\), for \\(2\\leq k\\leq m\\), where \\(m\\) is the length of a longest cycle in \\(D\\).

We prove the following new results. (a) Let \\(T\\) be a regular tournament of order \\(2n+1\\geq 11\\) and \\(S\\) a subset of \\(V(T)\\). Suppose that \\(|S|\\leq \\frac{1}{2}(n-2)\\) and \\(x\\), \\(y\\) are distinct vertices in \\(V(T)\\setminus S\\). If the subtournament \\(T-S\\) contains an \\((x,y)\\)-path of length \\(r\\), where \\(3\\leq r\\leq |V(T)\\setminus S|-2\\), then \\(T-S\\) also contains an \\((x,y)\\)-path of length \\(r+1\\). (b) Let \\(T\\) be an \\(m\\)-irregular tournament of order \\(p\\), i.e., \\(|d^+(x)-d^-(x)|\\le m\\) for every vertex \\(x\\) of \\(T.\\) If \\(m\\leq \\frac{1}{3}(p-5)\\) (respectively, \\(m\\leq \\frac{1}{5}(p-3)\\)), then for every pair of vertices \\(x\\) and \\(y\\), \\(T\\) has an \\((x,y)\\)-path of any length \\(k\\), \\(4\\leq k\\leq p-1\\) (respectively, \\(3\\leq k\\leq p-1\\) or \\(T\\) belongs to a family \\(\\cal G\\) of tournaments, which is defined in the paper). In other words, (b) means that if the semidegrees of every vertex of a tournament \\(T\\) of order \\(p\\) are between \\(\\frac{1}{3}(p+1)\\) and \\(\\frac{2}{3}(p-2)\\) (respectively, between \\(\\frac{1}{5}(2p-1)\\) and \\(\\frac{1}{5}(3p-4)\\)), then the claims in (b) hold. Our results improve in a sense related results of Alspach (1967), Jacobsen (1972), Alspach et al. (1974), Thomassen (1978) and Darbinyan (1977, 1978, 1979), and are sharp in a sense.