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

DOI10.1016/J.DAM.2016.02.010zbMATH Open1358.05124OpenAlexW1624522051MaRDI QIDQ516779FDOQ516779

Authors I. A. Karapetyan, Samvel Kh. Darbinyan 

Publication date 15 March 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.5643

zbMATH Keywords

digraphscyclesHamiltonian cycleslongest non-Hamiltonian cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: Let $D$ be a strong digraph on $ngeq4$ vertices. In [2, J. Graph Theory 22 (2) (1996) 181-187)], J. Bang-Jensen, G. Gutin and H. Li proved the following theorems: If (*) $d(x)+d(y)geq2n-1$ and $mind(x),d(y)geqn-1$ for every pair of non-adjacent vertices $x,y$ with a common in-neighbour or (**) $min{d}^{+}(x)+d^{-}(y),d^{-}(x)+d^{+}(y)geqn$ for every pair of non-adjacent vertices $x,y$ with a common in-neighbour or a common out-neighbour, then $D$ is hamiltonian. In this paper we show that: (i) if $D$ satisfies the condition (*) and the minimum semi-degree of $D$ at least two or (ii) if $D$ is not directed cycle and satisfies the condition (**), then either $D$ contains 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.

Recommendations

• Hamiltonian and long cycles in bipartite graphs with connectivity
• Long cycles in graphs without Hamiltonian paths
• On the size of maximally non-Hamiltonian digraphs
• Long cycles in Hamiltonian graphs
• On the structure of the set of cycle lengths in a Hamiltonian graph
• scientific article; zbMATH DE number 3985276
• On the set of cycle lengths in a Hamiltonian graph with a given maximum degree
• A Chvátal-Erdős condition for Hamilton cycles in digraphs
• Hamiltonian cycle properties in \(k\)-extendable non-bipartite graphs with high connectivity
• Longest cycles in certain bipartite graphs

Cites Work

• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3993611 (Why is no real title available?)
• scientific article; zbMATH DE number 908788 (Why is no real title available?)
• A classification of locally semicomplete digraphs
• A new sufficient condition for a digraph to be Hamiltonian
• A short proof of Meyniel's theorem
• A sufficient condition for the hamiltonian property of digraphs with large semi-degrees
• A theorem on pancyclic-oriented graphs
• An Ore-type condition implying a digraph to be pancyclic
• Cycles in digraphs– a survey
• Directed hamiltonian graphs
• Long Cycles in Digraphs
• On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li
• On pancyclic digraphs
• On the pancyclicity of digraphs with large semi-degrees
• Sufficient Conditions for Circuits in Graphs^†
• Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente

Cited In (2)

• Title not available (Why is no real title available?)
• On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li

This page was built for publication: On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516779)