Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Forbidden Pairs and the Existence of a Spanning Halin Subgraph

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

Abstract

AHalin graph is constructed from a plane embedding of a tree with no vertices of degree 2 by adding a cycle through its leaves in the natural order determined by the embedding. Halin graphs satisfy interesting properties. However, to our knowledge, there are no results giving a positive answer for “spanning Halin subgraph problem” (i.e., which graph has a Halin graph as a spanning subgraph) except for a conjecture by Lovász and Plummer which states that every 4-connected plane triangulation contains a spanning Halin subgraph. In this paper, we investigate the characterization of forbidden pairs guaranteeing the existence of a spanning Halin subgraph. In particular, we show that the set of such pairs is a very small class. Also, we show that\(\{ K_{1,3}, P_5 \}\) belongs to the set, but neither\(\{ K_{1,4}, P_5 \}\) nor\(\{ K_{1,3}, P_6 \}\) belongs to the set.

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
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28
Fig. 29

Similar content being viewed by others

References

  1. Bedrossian, P.: Forbidden subgraph and minimum degree conditions for Hamiltonicity. Ph.D. Thesis, Memphis State University (1991)

  2. Bondy, J.A.: Pancyclic graphs: recent results. In: Hajnal, A., Rado, R., Sós, V.T. (eds.) Infinite and finite sets, Colloq. Math. Soc. János Bolyai, vol. 10, pp. 181–187. Kiado, Budapest, North-Holland, Amsterdam (1975)

  3. Barefoot, C.A.: Hamiltonian connectivity of the Halin graphs. Congr. Numer.58, 93–102 (1987)

    MATH MathSciNet  Google Scholar 

  4. Broersma, H.J., Faudree, R.J., Huck, A., Trommel, H., Veldman, H.J.: Forbidden subgraphs that imply Hamiltonian-connectedness. J. Graph Theory40, 104–119 (2002)

    Article MATH MathSciNet  Google Scholar 

  5. Borie, R.B., Horton, S.B., Parker, R.G.: On some results pertaining to Halin graphs. Congr. Numer.89, 65–87 (1992)

    MATH MathSciNet  Google Scholar 

  6. Bondy, J.A., Lovász, L.: Lengths of cycles in Halin graphs. J. Graph Theory9, 397–410 (1985)

    Article MATH MathSciNet  Google Scholar 

  7. Chen, G., Enomoto, H., Ozeki, K., Tsuchiya, S.: Plane triangulations without spanning Halin subgraphs: counterexamples of Lovász–Plummer conjecture on Halin graphs. SIAM J. Discrete Math.29, 1423–1426 (2015)

    Article MATH MathSciNet  Google Scholar 

  8. Cornuéjols, G., Naddef, D., Pulleyblank, W.R.: Halin graphs and the travelling salesman prolblem. Math. Program.26, 287–294 (1983)

  9. Diemunsch, J., Furuya, M., Sharifzadeh, M., Tsuchiya, S., Wang, D., Wise, J., Yeager, E.: A characterization of\(P_5\)-free graphs with a homeomorphically irreducible spanning tree. Discrete Appl. Math.185, 71–78 (2015)

    Article MATH MathSciNet  Google Scholar 

  10. Faudree, J.R., Faudree, R.J., Ryjáček, Z., Vrána, P.: On forbidden pairs implying Hamilton-connectedness. J. Graph Theory72, 327–345 (2013)

    Article MATH MathSciNet  Google Scholar 

  11. Faudree, R.J., Gould, R.J.: Characterizing forbidden pairs for Hamiltonian properties. Discrete Math.173, 45–60 (1997)

    Article MATH MathSciNet  Google Scholar 

  12. Halin, R.: Studies on minimally\(n\)-connected graphs. In: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 129–136

  13. Lovász, L., Plummer, M.D.: On a family of planar bicritical graphs. Proc. Lond. Math. Soc. (3)30, 160–176 (1975)

    Article MATH MathSciNet  Google Scholar 

  14. Skowrońska, M.: The pancyclicity of Halin graphs and their exterior contractions. Ann. Discrete Math.27, 179–194 (1985)

    MATH MathSciNet  Google Scholar 

  15. Skupień, Z.: Crowned trees and planar highly Hamiltonian graphs. In: Contemporary Methods in Graph Theory, pp. 537–555. Wissenschaftsverlag, Mannheim (1990)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, Georgia State University, Atlanta, GA, 30303, USA

    Guantao Chen

  2. Faculty of Mathematics and Statistics, Central China Normal University, Wuhan, China

    Guantao Chen

  3. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, São Paulo, 05508-090, Brazil

    Jie Han

  4. Department of Applied Mathematics and Statistics, The State University of New York, Korea, Incheon, 21985, Korea

    Suil O

  5. Department of Mathematics, Vanderbilt University, Nashville, TN, 37240, USA

    Songling Shan

  6. School of Network and Information, Senshu University, 2-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa, 214-8580, Japan

    Shoichi Tsuchiya

Authors
  1. Guantao Chen

    You can also search for this author inPubMed Google Scholar

  2. Jie Han

    You can also search for this author inPubMed Google Scholar

  3. Suil O

    You can also search for this author inPubMed Google Scholar

  4. Songling Shan

    You can also search for this author inPubMed Google Scholar

  5. Shoichi Tsuchiya

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toShoichi Tsuchiya.

Additional information

Jie Han: Research partially supported by FAPESP (2014/18641-5, 2015/07869-8). Suil O: Research partially supported by National Research Foundation of Korea (NRF-2017R1D1A1B03031758). Shoichi Tsuchiya: Research partially supported by JSPS KAKENHI Grant number JP16K17646 and research grant of Senshu University.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, G., Han, J., O, S.et al. Forbidden Pairs and the Existence of a Spanning Halin Subgraph.Graphs and Combinatorics33, 1321–1345 (2017). https://doi.org/10.1007/s00373-017-1847-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