Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

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

Abstract

Letk be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at mostk branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of ordern has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at leastn − 2. These conditions are best possible. A related conjecture also is proposed.

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.

Similar content being viewed by others

References

  1. Broersma H., Tuinstra H.: Independence trees and Hamilton cycles. J. Graph Theory29, 227–237 (1998)

    Article MATH MathSciNet  Google Scholar 

  2. Flandrin E., Kaiser T., Kužel R., Li H., Ryjáček Z.: Neighborhood unions and extremal spanning trees. Discret. Math.308, 2343–2350 (2008)

    Article MATH  Google Scholar 

  3. Fujisawa J., Matsumura H., Yamashita T.: Degree bounded spanning trees. Graphs Combin.26, 695–720 (2010)

    Article MATH MathSciNet  Google Scholar 

  4. Gargano L., Hammar M.: There are spanning spiders in dense graphs (and we know how to find them). Lect. Notes Comput. Sci.2719, 802–816 (2003)

    Article MathSciNet  Google Scholar 

  5. Gargano L., Hammar M., Hell P., Stacho L., Vaccaro U.: Spanning spiders and light-splitting switches. Discret. Math.285, 83–95 (2004)

    Article MATH MathSciNet  Google Scholar 

  6. Gargano L., Hell P., Stacho L., Vaccaro U.: Spanning trees with bounded number of branch vertices. Lect. Notes Comput. Sci.2380, 355–365 (2002)

    Article MathSciNet  Google Scholar 

  7. Kano M., Kyaw A., Matsuda H., Ozeki K., Saito A., Yamashita T.: Spanning trees with small number of leaves in a claw-free graph. Ars. Combin.103, 137–154 (2012)

    MATH MathSciNet  Google Scholar 

  8. Matthews M.M., Sumner D.P.: Longest paths and cycles inK1,3-free graphs. J. Graph Theory9, 269–277 (1985)

    Article MATH MathSciNet  Google Scholar 

  9. Matsuda H., Matsumura H.: On ak-tree containing specified leaves in a graph. Graphs and Combin22, 371–381 (2006)

    Article MATH MathSciNet  Google Scholar 

  10. Neumann-Lara V., Rivera-Campo E.: Spanning trees with bounded degrees. Combinatorica11, 55–61 (1991)

    Article MATH MathSciNet  Google Scholar 

  11. Tsugaki M., Yamashita T.: Spanning trees with few leaves. Graphs Combin.23, 585–598 (2007)

    Article MATH MathSciNet  Google Scholar 

  12. Win S.: Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen (German). Abh. Math. Sem. Univ. Hamburg43, 263–267 (1975)

    Article MATH MathSciNet  Google Scholar 

  13. Win S.: On a conjecture of Las Vergnas concerning certain spanning trees in graphs. Result. Math.2, 215–224 (1979)

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama, 337-8570, Japan

    Haruhide Matsuda

  2. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

    Kenta Ozeki

  3. JST, ERATO, Kawarabayashi Large Graph Project, Tokyo, Japan

    Kenta Ozeki

  4. Department of Mathematics, Kinki University, 3-4-1 Kowakae, Higashiosaka, Osaka, 577-8502, Japan

    Tomoki Yamashita

Authors
  1. Haruhide Matsuda

    You can also search for this author inPubMed Google Scholar

  2. Kenta Ozeki

    You can also search for this author inPubMed Google Scholar

  3. Tomoki Yamashita

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toKenta Ozeki.

Rights and permissions

About this article

Cite this article

Matsuda, H., Ozeki, K. & Yamashita, T. Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph.Graphs and Combinatorics30, 429–437 (2014). https://doi.org/10.1007/s00373-012-1277-5

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