组合数学
数学
离散数学
光谱半径
生成树
图形
折线图
块图
最小生成树
连通支配集
路宽
连通性
齿轮图
距离遗传图
分裂图
1-平面图
对称图
特征向量
特雷莫克斯树
图形功率
电压图
图因式分解
可比性图
补图
作者
Chen Liu,Shuchao Li,Minjie Zhang
摘要
ABSTRACT The spanning tree packing number of a graph , written by , is defined as the maximum number of edge‐disjoint spanning trees. The study of is a classic problem in graph theory, and this parameter has important application in analyzing network robustness, routing optimization, and fault tolerance. Paul Seymour motivated the academia to establish the relationship between and eigenvalues of a connected graph. Let be the class of ‐vertex graphs with minimum degree and let denote the set of graphs of order and size admitting exactly edge‐disjoint spanning trees. Fan, Gu, and Lin [J. Graph Theory, 104 (2023) 697‐711] gave a sufficient size condition, together with its spectral analogue, to ensure that a graph satisfies under the condition . It is interesting to see that these problems are still open under the condition . In this paper, we fill this gap. Then we address an open problem posed by Fan, Gu, and Lin [J. Graph Theory, 104 (2023) 697‐711]: Determine the graphs among having maximum spectral radius. Furthermore, they conjectured that is the unique graph among attaining maximum spectral radius for and . We show that, for with is the unique graph among having maximum spectral radius. This resolves their open problem, and consequently disproves their conjecture.
科研通智能强力驱动
Strongly Powered by AbleSci AI