这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

Spanning k-trees and distance spectral radius in graphs

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Let \(k\ge 2\) be an integer. A tree T is called a k-tree if \(d_T(v)\le k\) for each \(v\in V(T)\); that is, the maximum degree of a k-tree is at most k. A k-tree T is a spanning k-tree if T is a spanning subgraph of a connected graph G. Let \(\lambda _1(D(G))\) denote the distance spectral radius in G, where D(G) denotes the distance matrix of G. In this paper, we verify an upper bound for \(\lambda _1(D(G))\) in a connected graph G to guarantee the existence of a spanning k-tree in G.

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+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Data availability

My manuscript has no associated data. No datasets were generated or analysed during the current study.

References

  1. Brouwer A, Haemers W (2005) Eigenvalues and perfect matchings. Linear Algebra Appl 395:155–162

    Article  MathSciNet  Google Scholar 

  2. Cioabǎ S, Gregory D, Haemers W (2009) Matchings in regular graphs from eigenvalue. J Combinat Theory Ser B 99:287–297

    Article  MathSciNet  Google Scholar 

  3. Li S, Zhang M (2012) On the signless Laplacian index of cacti with a given number of pendant vertices. Linear Algebra Appl 436:4400–4411

    Article  MathSciNet  Google Scholar 

  4. O S (2021) Spectral radius and matchings in graphs. Linear Algebra Appl 614:316–324

    Article  MathSciNet  Google Scholar 

  5. Zhang Y, Lin H (2021) Perfect matching and distance spectral radius in graphs and bipartite graphs. Discrete Appl Math 304:315–322

    Article  MathSciNet  Google Scholar 

  6. Ando K, Egawa Y, Kaneko A, Kawarabayashi K, Matsuda H (2002) Path factors in claw-free graphs. Discrete Math 243:195–200

    Article  MathSciNet  Google Scholar 

  7. Zhou S (2023) Degree conditions and path factors with inclusion or exclusion properties. Bulletin Mathematique de la Societe des Sciences Mathematiques de Roumanie 66(1):3–14

    MathSciNet  Google Scholar 

  8. Liu H (2022) Binding number for path-factor uniform graphs, proceedings of the romanian academy, series a: mathematics, physics, technical sciences, information. Science 23(1):25–32

    MathSciNet  Google Scholar 

  9. Zhou S, Sun Z, Liu H (2023) Some sufficient conditions for path-factor uniform graphs. Aequationes Mathematicae 97(3):489–500

    Article  MathSciNet  Google Scholar 

  10. Wang S, Zhang W (2022) Independence number, minimum degree and path-factors in graphs. Proc Romanian Acad Series Math Phys Techn Sci Info Sci 23(3):229–234

    MathSciNet  Google Scholar 

  11. Wu J (2022) Path-factor critical covered graphs and path-factor uniform graphs. RAIRO Oper Res 56(6):4317–4325

    Article  MathSciNet  Google Scholar 

  12. Zhou S (2023) Some results on path-factor critical avoidable graphs. Discussiones Mathematicae Graph Theory 43(1):233–244

    Article  MathSciNet  Google Scholar 

  13. Gao W, Chen Y, Wang Y (2021) Network vulnerability parameter and results on two surfaces. Int J Intell Syst 36:4392–4414

    Article  Google Scholar 

  14. Zhou S, Zhang Y, Sun Z (2024) The \(A_{\alpha }\)-spectral radius for path-factors in graphs. Discrete Math 347(5):113940

    Article  MathSciNet  Google Scholar 

  15. Zhou S, Sun Z, Liu H (2024) Distance signless Laplacian spectral radius for the existence of path-factors in graphs. Aequationes Mathematicae 98(3):727–737

    Article  MathSciNet  Google Scholar 

  16. Zhou S, Wu J, Bian Q (2022) On path-factor critical deleted (or covered) graphs. Aequationes Mathematicae 96(4):795–802

    Article  MathSciNet  Google Scholar 

  17. Kouider M (2013) Sufficient condition for the existence of an even \([a, b]\)-factor in graph. Graphs Combinat 29(4):1051–1057

    Article  MathSciNet  Google Scholar 

  18. Kouider M, Lonc Z (2004) Stability number and \([a, b]\)-factors in graphs. J Graph Theory 46(4):254–264

    Article  MathSciNet  Google Scholar 

  19. Wang S, Zhang W (2024) Some results on star-factor deleted graphs. Filomat 38(3):1101–1107

    MathSciNet  Google Scholar 

  20. Wu J (2024) A sufficient condition for the existence of fractional \((g, f, n)\)-critical covered graphs. Filomat 38(6):2177–2183

    MathSciNet  Google Scholar 

  21. Zhou S, Liu H (2023) Two sufficient conditions for odd \([1, b]\)-factors in graphs. Linear Algebra Appl 661:149–162

    Article  MathSciNet  Google Scholar 

  22. Zhou S (2022) A neighborhood union condition for fractional \((a, b, k)\)-critical covered graphs. Discrete Appl Math 323:343–348

    Article  MathSciNet  Google Scholar 

  23. Zhou S (2024) Remarks on restricted fractional \((g, f)\)-factors in graphs. Discrete Appl Math 354:271–278

    Article  MathSciNet  Google Scholar 

  24. Zhou S, Zhang Y (2024) Sufficient conditions for fractional \([a,b]\)-deleted graphs. Indian J Pure Appl Math. https://doi.org/10.1007/s13226-024-00564-w

  25. Zhou S, Pan Q, Xu L (2023) Isolated toughness for fractional \((2, b, k)\)-critical covered graphs. Proc Romanian Acad Series Math Phys Tech Sci Info Sci 24(1):11–18

    MathSciNet  Google Scholar 

  26. Zhou S, Pan Q, Xu Y (2024) A new result on orthogonal factorizations in networks. Filomat 38(20) (in press)

  27. Zhou S, Zhang Y, Liu H (2024), Some properties of \((a,b,k)\)-critical graphs. Filomat 38(16) (in press)

  28. Ding G, Johnson T, Seymour P (2001) Spanning trees with many leaves. J Graph Theory 37(4):189–197

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  30. Kyaw A (2001) A sufficient condition for a graph to have a \(k\)-tree. Graphs Combinat 17:113–121

    Article  MathSciNet  Google Scholar 

  31. Neumann-Lara V, Rivera-Campo E (1991) Spanning trees with bounded degrees. Combinatorica 11(1):55–61

    Article  MathSciNet  Google Scholar 

  32. Gu X, Liu M (2022) A tight lower bound on the matching number of graphs via Laplacian eigenvalues. Eur J Combinat 101:103468

    Article  MathSciNet  Google Scholar 

  33. Fan D, Goryainov S, Huang X, Lin H (2021) The spanning \(k\)-trees, perfect matchings and spectral radius of graphs. Linear Multilinear Algebra. https://doi.org/10.1080/03081087.2021.1985055

  34. Godsil C (1993) Algebraic combinatorics. Chapman and Hall Mathematics Series, New York

    Google Scholar 

  35. Brouwer A Haemers W (2011) Spectra of graphs—monograph. Springer

  36. You L, Yang M, So W, Xi W (2019) On the spectrum of an equitable quotient matrix and its application. Linear Algebra Appl 577:21–40

    Article  MathSciNet  Google Scholar 

  37. Win S (1989) On a connection between the existence of \(k\)-trees and the toughness of a graph. Graphs Combinat 5:201–205

    Article  MathSciNet  Google Scholar 

  38. Ellingham M, Zha X (2000) Toughness, trees, and walks. J Graph Theory 33(3):125–137

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to show their great gratitude to anonymous referees for the valuable suggestions which largely improve the quality and the readability of this paper. Project ZR2023MA078 supported by Shandong Provincial Natural Science Foundation.

Author information

Authors and Affiliations

  1. School of Science, Jiangsu University of Science and Technology, Zhenjiang, 212100, Jiangsu, China

    Sizhong Zhou & Jiancheng Wu

Authors
  1. Sizhong Zhou
    View author publications

    Search author on:PubMed Google Scholar

  2. Jiancheng Wu
    View author publications

    Search author on:PubMed Google Scholar

Contributions

All authors reviewed the manuscript.

Corresponding author

Correspondence to Sizhong Zhou.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest to this work.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhou, S., Wu, J. Spanning k-trees and distance spectral radius in graphs. J Supercomput 80, 23357–23366 (2024). https://doi.org/10.1007/s11227-024-06355-8

Download citation

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11227-024-06355-8

Keywords

Mathematics Subject Classification