A sufficient condition for oriented graphs to be Hamiltonian

DOI10.1016/0012-365X(86)90141-XMaRDI QIDQ1079579zbMATH OpenFDO

Authors Odile Favaron, Oscar Ordaz

Publication date 1986

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(86)90141-X

zbMATH Keywords

conjectureHamiltonian cyclek-conneted oriented graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Review text

The authors conjecture that every k-conneted oriented graph with n vertices and more than \(n(n-1)-k(k+1)\) arcs has a Hamiltonian cycle. The conjecture is best possible for \(n>3k\) and in the present paper it is verified for \(k=2\).

Recommendations

• scientific article; zbMATH DE number 147645
• A new sufficient condition for a digraph to be Hamiltonian
• Hamilton Cycles in Oriented Graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• A sufficient condition for Hamiltonian cycles in \(C_n XC_m-S_k\)

Cites work

• A Chvátal-Erdős condition for (1,1)-factors in digraphs
• Cycles in digraphs– a survey
• Cycles in strong oriented graphs
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• Graph theory
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• Long Cycles in Digraphs
• Number of arcs and cycles in digraphs
• On cycles and paths in digraphs

Cited in

(8)

• A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• scientific article; zbMATH DE number 147645 (Why is no real title available?)
• k-Arc Hamilton graphs
• scientific article; zbMATH DE number 1472153 (Why is no real title available?)
• scientific article; zbMATH DE number 1792615 (Why is no real title available?)
• A sufficient condition for Hamiltonian cycles in \(C_n XC_m-S_k\)
• Beyond quasi-adjoint graphs: on polynomial-time solvable cases of the Hamiltonian cycle and path problems

This page was built for publication: A sufficient condition for oriented graphs to be Hamiltonian

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