Bipancyclicism and bipanconnectivity in bipartite graphs

Zhiquan Hu and Yan Zou

Applied Mathematics and Computation, 2020, vol. 377, issue C

Abstract: 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.

Keywords: Edge prorating number; Path two bipancyclic; Bipanconnected; Bipartite graph (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300320301181
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:377:y:2020:i:c:s0096300320301181

DOI: 10.1016/j.amc.2020.125149

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().