错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Characterizing spanning trees via the size or the spectral radius of graphs

  • Jie Wu

摘要

Let G be a connected graph and let \(k\ge 1\) k 1 be an integer. Let T be a spanning tree of G. The leaf degree of a vertex \(v\in V(T)\) v V ( T ) is defined as the number of leaves adjacent to v in T. The leaf degree of T is the maximum leaf degree among all the vertices of T. Let |E(G)| and \(\rho (G)\) ρ ( G ) denote the size and the spectral radius of G, respectively. In this paper, we first create a lower bound on the size of G to ensure that G admits a spanning tree with leaf degree at most k. Then we establish a lower bound on the spectral radius of G to guarantee that G contains a spanning tree with leaf degree at most k. Finally, we create some extremal graphs to show all the bounds obtained in this paper are sharp.