Extremal digraphs on Meyniel-type condition for Hamiltonian cycles in balanced bipartite digraphs

DOI10.46298/DMTCS.5851MaRDI QIDQ5024671zbMATH OpenOpenAlexFDO

Authors Ruixia Wang, Linxin Wu, Wei Meng

Publication date 27 January 2022

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.05542, https://dmtcs.episciences.org/8937

zbMATH Keywords

bipartite digraphdegree sum conditionHamiltonian cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Abstract: Let $D$ be a strong balanced digraph on $2a$ vertices. Adamus et al. have proved that $D$ is hamiltonian if $d(u)+d(v)ge3a$ whenever $uvotinA(D)$ and $vuotinA(D)$. The lower bound $3a$ is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if $d(u)+d(v)geq3a-1$ whenever $uvotinA(D)$ and $vuotinA(D)$, then $D$ is traceable. The lower bound $3a-1$ is tight.

Recommendations

• On the Meyniel condition for Hamiltonicity in bipartite digraphs
• Extremal digraphs on Woodall‐type condition for Hamiltonian cycles in balanced bipartite digraphs
• A sufficient condition for a balanced bipartite digraph to be Hamiltonian
• A note on dominating pair degree condition for Hamiltonian cycles in balanced bipartite digraphs
• A degree sum condition for Hamiltonicity in balanced bipartite digraphs

Cites work

• A degree condition for cycles of maximum length in bipartite digraphs
• A degree sum condition for Hamiltonicity in balanced bipartite digraphs
• A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs
• A note on cycles of maximum length in bipartite digraphs
• A sufficient condition for a balanced bipartite digraph to be Hamiltonian
• Cycles and paths in bipartite tournaments with spanning configurations
• scientific article; zbMATH DE number 7225861 (Why is no real title available?)
• scientific article; zbMATH DE number 3859163 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 908788 (Why is no real title available?)
• New sufficient conditions for bipancyclicity of balanced bipartite digraphs
• On the Meyniel condition for Hamiltonicity in bipartite digraphs
• Sufficient conditions for Hamiltonian cycles in bipartite digraphs
• Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente

Cited in

(5)

• A note on dominating pair degree condition for Hamiltonian cycles in balanced bipartite digraphs
• A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs
• On the Meyniel condition for Hamiltonicity in bipartite digraphs
• Extremal digraphs on Woodall‐type condition for Hamiltonian cycles in balanced bipartite digraphs
• A new sufficient condition for a 2-strong digraph to be Hamiltonian

This page was built for publication: Extremal digraphs on Meyniel-type condition for Hamiltonian cycles in balanced bipartite digraphs

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