2012/08/10 by Janusz Adamus, Adamus, Janusz, Lech Adamus +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C20 #msc:05C38 #msc:05C45
paper · pdf · doi:10.48550/arxiv.1208.2164
17 pages
arxiv created 2012/08/10 · arxiv updated 2012/08/13
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.