Bipancyclicism and bipanconnectivity in bipartite graphs

摘要

Given a bipartite graph G=(A1,A2,E) with m ≔ min {|A1|, |A2|} ≥ 2, the edge prorating number for x ∈ Ai is defined as ρG(x)=(d(x)−1)/|A3−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 ℓ ∈ [2, 2m], G has a u, v-path of length ℓ. 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.