Abstract
Let G = (V 1, V 2, E) be a balanced bipartite graph with 2n vertices. The bipartite binding number of G, denoted by B(G), is defined to be n if G = K n and \(\mathop {\min }\limits_{i \in \left\{ {1,2} \right\}} \mathop {\min }\limits_{\O \ne S \subseteq {V_{I,}}\left| {N\left( S \right)} \right| \prec n} \left| {N\left( S \right)} \right|/\left| S \right|\) otherwise. We call G bipancyclic if it contains a cycle of every even length m for 4 m 2n. A theorem showed that if G is a balanced bipartite graph with 2n vertices, B(G) > 3/2 and n 139, then G is bipancyclic. This paper generalizes the conclusion as follows: Let 0 < c < 3/2 and G be a 2-connected balanced bipartite graph with 2n (n is large enough) vertices such that B(G) c and δ(G) (2 - c)n/(3 - c) + 2/3. Then G is bipancyclic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy J A, Murty U S R. Graph Theory with Applications [M]. New York: Macmillan, 1976.
Shi R. The binding number of a graph and its pancyclism [J]. Acta Mathematicae Applicatae Sinica, 1987, 3(3): 257–269.
Woodall D R. The binding number of a graph and its Anderson number [J]. Journal of Combinatorial Theory Series B, 1973, 15(3): 225–255.
Bauer D, Schmeichel E. binding number, minimum degree, and cycle structure in graphs [J]. Journal of Graph Theory, 2012, 71(2): 219–228.
Hu Z, Law K, Zang W. An optimal Binding number condition for bipancyclism [J]. SIAM Journal on Discrete Mathematics, 2013, 27(2): 597–618.
Hu Z Q, Sun J. Weakly bipancyclic bipartite graphs [J]. Discrete Applied Mathematics, 2015, 194(2): 102–120.
Sun J, Hu Z Q. A sufficient condition for Hamiltonian in balanced bipartite graphs [J]. Acta Mathematicae Applicatae Sinica, 2015, 38(5): 796–805(Ch).
Ash P. Dominating Cycles, Hamilton Cycles and Cycles with Many Chords in 2-Connected Graphs [D]. London: Goldsmiths College, 1985.
Jackson B, Li H. Hamilton cycles in 2-connected regular bipartite graphs [J]. Journal of Combinatorial Theory Series B, 1994, 62(2): 236–258.
Author information
Authors and Affiliations
Corresponding author
Additional information
Foundation item: Supported by the Scientific Research Fund of Hubei Provincial Education Department (B2015021)
Rights and permissions
About this article
Cite this article
Sun, J., Hu, Z. Binding number, minimum degree and bipancyclism in bipartite graphs. Wuhan Univ. J. Nat. Sci. 21, 448–452 (2016). https://doi.org/10.1007/s11859-016-1195-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11859-016-1195-0