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

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

Samvel Kh. Darbinyan, I. A. Karapetyan

Publication date: 15 March 2017

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

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.

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

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

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)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• 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)