Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Bipartite Independent Number and Hamilton-Biconnectedness of Bipartite Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

LetG be a balanced bipartite graph with bipartite setsX, Y. We say thatG is Hamilton-biconnected if there is a Hamilton path connecting any vertex inX and any vertex inY. We define the bipartite independent number\(\alpha ^o_B(G)\) to be the maximum integer\(\alpha \) such that for any integer partition\(\alpha =s+t\),G has an independent set formed bys vertices inX andt vertices inY. In this paper we show that if\(\alpha ^o_B(G)\le \delta (G)\) thenG is Hamilton-biconnected, unlessG has a special construction.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Amar, D., Favaron, O., Mago, P., Ordaz, O.: Biclosure and bistability in a balanced bipartite graph. J. Graph Theory20(4), 513–529 (1995)

    Article MathSciNet  Google Scholar 

  2. Ash, P.: Two sufficient conditions for the existence of Hamilton cycles in bipartite graphs. Ars Combin.16, 33–37 (1983)

    MathSciNet MATH  Google Scholar 

  3. Bagga, K.S., Varma, B.N.: Bipartite graphs and degree conditions. In: Alavi, Y., Chung, F., Graham, R., Hsu, D., Siam, G. (eds.) Graph Theory, Combinatorics, Algorithms, and Applications, pp. 564–573. Springer, New York (1991)

    MATH  Google Scholar 

  4. Bondy, J.A., Chvátal, V.: A method in graph theory. Discrete Math.15, 111–135 (1976)

    Article MathSciNet  Google Scholar 

  5. Chvátal, V., Erdős, P.: A note on hamiltonian circuits. Discrete Math.2, 111–113 (1972)

    Article MathSciNet  Google Scholar 

  6. Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3)2, 69–81 (1952)

    Article MathSciNet  Google Scholar 

  7. Favaron, O., Mago, P., Maulino, C., Ordaz, O.: Hamiltonian properties of bipartite graphs and digraphs with bipartite independence number 2. SIAM J. Discrete Math.6, 189–196 (1993)

    Article MathSciNet  Google Scholar 

  8. Favaron, O., Mago, P., Ordaz, O.: On the bipartite independence number of a balanced bipartite graph. Discrete Math.121, 55–63 (1993)

    Article MathSciNet  Google Scholar 

  9. Fraisse, P.:\(D_\lambda \)-cycles and Their Applications for Hamiltonian Graphs, Ph.D. thesis, Université Paris-Sud, Paris, France, (1986)

  10. Gould, R.J.: Updating the hamiltonian problem—a survey. J. Graph Theory15(2), 121–157 (1991)

    Article MathSciNet  Google Scholar 

  11. Locke, S.C.: A generalization of Dirac’s Theorem. Combinatorica5(2), 149–159 (1985)

    Article MathSciNet  Google Scholar 

  12. Lu, X.: Hamiltonian cycles in bipartite graphs. Combinatorica15(2), 247–254 (1995)

    Article MathSciNet  Google Scholar 

  13. Moon, J., Moser, L.: On Hamiltonian bipartite graphs. Israel J. Math.1, 163–165 (1963)

    Article MathSciNet  Google Scholar 

  14. Ore, O.: Note on hamiltonian circuits. Am. Math. Mon.67, 55 (1960)

    Article  Google Scholar 

  15. Simmons, G.J.: Almost all\(n\)-dimensional rectangular lattices are hamilton-laceable, In: Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, Fla., pp. 649-661 (1978)

  16. Simmons, G.J.: Minimal Hamilton-laceable graphs. Congr. Numer.29, 893–900 (1980)

    MathSciNet MATH  Google Scholar 

  17. Simmons, G.J.: Maximal non-hamilton-laceable graphs. J. Graph Theory5(4), 407–415 (1981)

    Article MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an, 710129, People’s Republic of China

    Binlong Li

  2. Xi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an, 710129, People’s Republic of China

    Binlong Li

Authors
  1. Binlong Li

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toBinlong Li.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supported by NSFC (11601429) and the Fundamental Research Funds for the Central Universities (3102019ghjd003).

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, B. Bipartite Independent Number and Hamilton-Biconnectedness of Bipartite Graphs.Graphs and Combinatorics36, 1639–1653 (2020). https://doi.org/10.1007/s00373-020-02211-7

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp