SUFFICIENT CONDITIONS FOR SPANNING TREES WITH CONSTRAINED LEAF DISTANCE IN A GRAPH

被引：2

作者：

Chen, Hongzhang ^{[1
]}

Lv, Xiaoyun ^{[1
]}

Li, Jianxi ^{[2
]}

Xu, Shou-Jun ^{[1
,2
]}

机构：

[1] Lanzhou Univ, Gansu Ctr Appl Math, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China

[2] Minnan Normal Univ, Sch Math & Stat, Zhangzhou 363000, Fujian, Peoples R China

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2025年 / 45卷 / 01期

关键词：

spanning tree; leaf distance; (signless Laplacian) spectral radius;

D O I：

10.7151/dmgt.2530

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The leaf distance of a tree is the minimum of distances between any two leaves of a tree. It is well known that seeking sufficient conditions for a graph to have some special kinds of spanning trees is an interesting and popular problem. In this paper, we first provide a lower bound on the size of a graph G to guarantee that G has a spanning tree with leaf distance at least 4. Moreover, for any graph G with minimum degree delta, we also deduce a lower bound on the spectral radius (or the signless Laplacian spectral radius) of G to ensure the existence of a spanning tree with leaf distance of at least 4 in G.

引用

页码：253 / 266

页数：14

共 13 条

[1]

Akiyama J, 2011, LECT NOTES MATH, V2031, P1, DOI 10.1007/978-3-642-21919-1

[2] Spectral radius and spanning trees of graphs [J].

Ao, Guoyan ;

Liu, Ruifang ;

Yuan, Jinjiang .

DISCRETE MATHEMATICS, 2023, 346 (08)

[3]

Bapat R.B., 2010, Graphs and Matrices, DOI DOI 10.1007/978-1-84882-981-7

[4]

Bondy J. A., 1976, Graph theory with applications

[5] The spanning k-trees, perfect matchings and spectral radius of graphs [J].

Fan, Dandan ;

Goryainov, Sergey ;

Huang, Xueyi ;

Lin, Huiqiu .

LINEAR & MULTILINEAR ALGEBRA, 2022, 70 (21) :7264-7275

[6] Spanning trees with constraints on the leaf degree [J].

Kaneko, A .

DISCRETE APPLIED MATHEMATICS, 2001, 115 (1-3) :73-76

[7] Spanning trees with leaf distance at least four [J].

Kaneko, Atsushi ;

Kano, M. ;

Suzuki, Kazuhiro .

JOURNAL OF GRAPH THEORY, 2007, 55 (01) :83-90

[8] Spanning Trees: A Survey [J].

Ozeki, Kenta ;

Yamashita, Tomoki .

GRAPHS AND COMBINATORICS, 2011, 27 (01) :1-26

[9] Spectral radius and matchings in graphs [J].

Suil, O. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 614 :316-324

[10] ON A CONNECTION BETWEEN THE EXISTENCE OF K-TREES AND THE TOUGHNESS OF A GRAPH [J].

WIN, S .

GRAPHS AND COMBINATORICS, 1989, 5 (02) :201-205

← 1 2 →