Sufficient conditions for Hamiltonian cycles in bipartite digraphs

DOI10.1016/J.DAM.2018.11.024MaRDI QIDQ1732099zbMATH OpenOpenAlexFDO

Authors Samvel Kh. Darbinyan

Publication date 22 March 2019

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

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

zbMATH Keywords

Hamiltonian cyclesperfect matchingbipartite digraphslongest non-Hamiltonian cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove two sharp sufficient conditions for hamiltonian cycles in balanced bipartite directed graph. Let $D$ be a strongly connected balanced bipartite directed graph of order $2a$. Let $x,y$ be distinct vertices in $D$. $x,y$ dominates a vertex $z$ if $xightarrowz$ and $yightarrowz$; in this case, we call the pair $x,y$ dominating. (i) {it If $ageq4$ and $maxd(x),d(y)geq2a-1$ for every dominating pair of vertices $x,y$, then either $D$ is hamiltonian or $D$ is isomorphic to one exceptional digraph of order eight.} (ii) {it If $ageq5$ and $d(x)+d(y)geq4a-3$ for every dominating pair of vertices $x,y$, then $D$ is hamiltonian.} The first result improves a theorem of R. Wang (arXiv:1506.07949 [math.CO]), the second result, in particular, establishes a conjecture due to Bang-Jensen, Gutin and Li (J. Graph Theory , 22(2), 1996) for strongly connected balanced bipartite digraphs of order at least ten.

Recommendations

• A sufficient condition for a balanced bipartite digraph to be Hamiltonian
• A degree sum condition for Hamiltonicity in balanced bipartite digraphs
• scientific article; zbMATH DE number 5931607
• On the Meyniel condition for Hamiltonicity in bipartite digraphs
• scientific article; zbMATH DE number 7225861

Cites work

• scientific article; zbMATH DE number 3425637 (Why is no real title available?)
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3859163 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 908788 (Why is no real title available?)
• scientific article; zbMATH DE number 3310759 (Why is no real title available?)
• A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs
• A degree condition for cycles of maximum length in bipartite digraphs
• A degree sum condition for Hamiltonicity in balanced bipartite digraphs
• A new sufficient condition for a digraph to be Hamiltonian
• A short proof of Meyniel's theorem
• A sufficient condition for a balanced bipartite digraph to be Hamiltonian
• A sufficient condition for maximum cycles in bipartite digraphs
• A sufficient condition for the hamiltonian property of digraphs with large semi-degrees
• A survey on Hamilton cycles in directed graphs
• Cycles and paths in bipartite tournaments with spanning configurations
• Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
• Cycles and paths of many lengths in bipartite digraphs
• Cycles in digraphs– a survey
• Directed hamiltonian graphs
• Long Cycles in Digraphs
• On the Meyniel condition for Hamiltonicity in bipartite digraphs
• Sufficient Conditions for Circuits in Graphs^†
• Sufficient conditions for a balanced bipartite digraph to be even pancyclic
• Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente

Cited in

(21)

• Applying a condition for a Hamiltonian bipartite graph to be bipancyclic
• scientific article; zbMATH DE number 3859163 (Why is no real title available?)
• Hamiltonian cycles in a generalization of bipartite tournaments with a cycle factor
• A degree condition for cycles of maximum length in bipartite digraphs
• scientific article; zbMATH DE number 5931607 (Why is no real title available?)
• The structure of 2-colored best match graphs
• A degree sum condition for Hamiltonicity in balanced bipartite digraphs
• A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs
• On the Meyniel condition for Hamiltonicity in bipartite digraphs
• A sufficient condition for a balanced bipartite digraph to be Hamiltonian
• scientific article; zbMATH DE number 426372 (Why is no real title available?)
• Extremal digraphs on Woodall‐type condition for Hamiltonian cycles in balanced bipartite digraphs
• scientific article; zbMATH DE number 4177106 (Why is no real title available?)
• A sufficient condition for Hamiltonians in balanced bipartite graphs
• Extremal digraphs on Meyniel-type condition for Hamiltonian cycles in balanced bipartite digraphs
• A note on dominating pair degree condition for Hamiltonian cycles in balanced bipartite digraphs
• On dominating pair degree conditions for Hamiltonicity in balanced bipartite digraphs
• Some results on the existence of Hamiltonian cycles in \(\mathcal{P} \)-compositions of bipartite digraphs
• Sufficient conditions for a balanced bipartite digraph to be even pancyclic
• Directed Hamilton cycles in digraphs and matching alternating Hamilton cycles in bipartite graphs
• scientific article; zbMATH DE number 3847429 (Why is no real title available?)

This page was built for publication: Sufficient conditions for Hamiltonian cycles in bipartite digraphs

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