Sufficient conditions for Hamiltonian cycles in bipartite digraphs

DOI10.1016/J.DAM.2018.11.024zbMATH Open1407.05138arXiv1604.08733OpenAlexW2904600371MaRDI QIDQ1732099FDOQ1732099

Authors: Samvel Kh. Darbinyan 

Publication date: 22 March 2019

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

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.

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

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

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)

Cites Work

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

Cited In (21)

• Title not available (Why is that?)
• Applying a condition for a Hamiltonian bipartite graph to be bipancyclic
• Hamiltonian cycles in a generalization of bipartite tournaments with a cycle factor
• A degree condition for cycles of maximum length in bipartite digraphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Extremal digraphs on Woodall‐type condition for Hamiltonian cycles in balanced bipartite digraphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)