pith. sign in

arxiv: 1208.2164 · v1 · pith:JAADWUEMnew · submitted 2012-08-10 · 🧮 math.CO

On the Meyniel condition for hamiltonicity in bipartite digraphs

classification 🧮 math.CO
keywords bipartitedigraphhamiltonicityverticesbalancedconditiondegreehamiltonian
0
0 comments X
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.