Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions

Wang, Ruixia  ; Wu, Linxin

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 245-267

Résumé

In 2017, Adamus proved that a strong balanced bipartite digraph of order 2a with a≥ 3 is hamiltonian, if d(u)+d(v)≥ 3a for every pair of dominating or dominated vertices {u,v}. In this paper, we characterize all non-hamiltonian bipartite digraphs when d(u)+d(v)≥ 3a-1 for every pair of dominating or dominated vertices {u,v}, consisting of one infinite family and four exceptional bipartite digraphs of order six. Using this result, we also prove that a strong balanced bipartite digraph of order 2a with a≥ 4 contains all cycles of lengths 2, 4, …, 2a-2 except for a single bipartite digraph, and also contains a hamiltonian path, if d(u)+d(v)≥ 3a-1 for every pair of dominating or dominated vertices {u, v}. The bounds for 3a-1 in two results are sharp. This partly settles the following problem when l=a-1 proposed by Adamus [A Meyniel-type condition for bipancyclicity in balanced bipartitie digraphs, Graphs Combin. 34 (2018) 703–709]. Whether for every 1≤ l lt; a there is a k(l), k(l)≥ 1, such that every strong balanced bipartite digraph of order 2a contains cycles of lengths 2, 4, …, 2l, whenever d(u)+d(v)≥ 3a-k(l) for every pair of dominating or dominated vertices {u, v}.

Détail

Keywords: bipartite digraph, degree sum, bipancyclicity, hamiltonian cycle