A new sufficient condition for a digraph to be Hamiltonian
The following famous theorem is due to Meyniel: Every strongly connected digraph \(D\) of order \(n\) with the property that \(d(x)+ d(y)\geq 2n-1\), for every pair \((x,y)\) of non-adjacent vertices, is Hamiltonian. \textit{J. Bang-Jensen}, \textit{G. Gutin} and \textit{H. Li} [J. Graph Theory 22, No. 2, 181-187 (1996; Zbl 0854.05067)] conjectured that it suffices to consider only pairs \((x,y)\) such that \(x\), \(y\) dominate or are dominated by a vertex in \(D\) (and \(D\) remains Hamiltonian). In this paper, it is proved that if one replaces \(2n-1\) with \({5\over 2} n-4\) then \(D\) is indeed Hamiltonian. Some other results supporting the above conjecture are also proved.
- Pancyclism and Meyniel's conditions
- A sufficient condition for oriented graphs to be Hamiltonian
- Notes on sufficient conditions for a graph to be hamiltonian
- Cycles through large degree vertices in digraphs: A generalization of Meyniel's theorem
- Quasi-Hamiltonicity: A series of necessary conditions for a digraph to be Hamiltonian
- Sufficient conditions for a balanced bipartite digraph to be even pancyclic
- Sufficient conditions for Hamiltonian cycles in bipartite digraphs
- A dominated pair condition for a digraph to be Hamiltonian
- A degree sum condition for Hamiltonicity in balanced bipartite digraphs
- A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs
- scientific article; zbMATH DE number 7225861 (Why is no real title available?)
- A sufficient condition for a digraph to be Hamiltonian
- Directed hamiltonian graphs
- A survey on Hamilton cycles in directed graphs
- scientific article; zbMATH DE number 1334635 (Why is no real title available?)
- A sufficient condition for the hamiltonian property of digraphs with large semi-degrees
- Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs
- scientific article; zbMATH DE number 908788 (Why is no real title available?)
- A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture
- New necessary and sufficient condition and algorithm for directed hamiltonian graph based on boolean determinant theory
- On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li
- Preface
- A new sufficient condition for a 2-strong digraph to be Hamiltonian
- A new sufficient condition for hamiltonicity of graphs
- A sufficient condition for cyclability in directed graphs
This page was built for publication: A new sufficient condition for a digraph to be Hamiltonian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1302145)
