On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li

详细信息    查看全文

• 作者：S.Kh. Darbinyan ; ^{samdarbin@ipia.sci.am} ; I.A. Karapetyan ^{isko@ipia.sci.am}
• 关键词：Digraphs ; Cycles ; Hamiltonian cycles ; Longest non-Hamiltonian cycles
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P3
• 页码：537-549
• 全文大小：470 K
• 卷排序：216

文摘

Let DD be a strongly connected directed graph of order n≥4n≥4. In Bang-Jensen et al. (1996), (J. of Graph Theory 22 (2) (1996) 181–187), J. Bang-Jensen, G. Gutin and H. Li proved the following theorems: If (∗)(∗)d(x)+d(y)≥2n−1d(x)+d(y)≥2n−1 and min{d(x),d(y)}≥n−1min{d(x),d(y)}≥n−1 for every pair of non-adjacent vertices x,yx,y with a common in-neighbour or (∗∗)min{d+(x)+d−(y),d−(x)+d+(y)}≥n for every pair of non-adjacent vertices x,yx,y with a common in-neighbour or a common out-neighbour, then DD is Hamiltonian. In this paper we show that: (i) if DD satisfies condition (∗)(∗) and the minimum semi-degree of DD at least two or (ii) if DD is not directed cycle and satisfies condition (∗∗)(∗∗), then either DD contains a cycle of length n−1n−1 or nn is even and DD is isomorphic to the complete bipartite digraph or to the complete bipartite digraph minus one arc.