Bipancyclicism and bipanconnectivity in bipartite graphs
Abstract Given a bipartite graph G = ( A 1 , A 2 , E ) with m ≔ min {|A1|, |A2|} ≥ 2, the edge prorating number for x ∈ Ai is defined as ρ G ( x ) = ( d ( x ) − 1 ) / | A 3 − i | , i = 1 , 2 . Set ρ(G) ≔ min {ρG(x): x ∈ A1 ∪ A2} and call it the minimum edge prorating number of G. We call G path two bipancyclic if for every path P of length two in G, and for every integer k ∈ [2, m], G has a 2k-cycle passing through P. In this article, it is shown that the minimum edge prorating number condition ρ(G) ≥ 1/2 implies that a bipartite graph G is either path two bipancyclic or isomorphic to G2n,4, where n ≥ 3 and G2n,4 is a 2n by 4 bipartite graph. As an application, we proved that the minimum edge prorating number condition ρ(G) ≥ 1/2 also implies the bipanconnectivity of a bipartite graph G: for every pair u, v of distinct vertices, and for every appropriate integer l ∈ [2, 2m], G has a u, v-path of length l. This unifies the known results in Tian and Zang (1989) and Du et al. (2018). Examples show that the minimum edge prorating number condition ρ(G) ≥ 1/2 in both of our results are sharp.