On the Meyniel condition for hamiltonicity in bipartite digraphs
classification
🧮 math.CO
keywords
bipartitedigraphhamiltonicityverticesbalancedconditiondegreehamiltonian
read the original abstract
We prove a sharp Meyniel-type criterion for hamiltonicity of a balanced bipartite digraph: For k greater than or equal to 2, a bipartite digraph D with colour classes of cardinalities k is hamiltonian if the sum of degrees of vertices u and v is at least 3k+1 for every pair of vertices u, v such that D does not contain the arc uv nor vu. As a consequence, we obtain a sharp sufficient condition for hamiltonicity in terms of the minimal degree: a balanced bipartite digraph D on 2k vertices is hamiltonian if its minimal degree is at least (3k + 1)/2.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.