连通图的补图谱半径与支撑k树
Spanning k-trees and the Spectral Radius of Complements of Connected Graphs
令G是简单连通图。设G有支撑树T，如果对于任意一点$v \in V(T)$都有$d_{T}(v) \leqslant k$，则称G存在支撑k树。令A(G)为G的邻接矩阵，则Gc的邻接矩阵为$A\left(G^{c}\right)=J_{n}-I_{n}-A(G).令\rho\left(G^{c}\right)$为矩阵$A\left(G^{c}\right)$的最大特征值，也称作Gc的谱半径。令$G^{*} \cong K_{1} \vee\left(K_{n-k-1} \cup k K_{1}\right)$，并且$n \geqslant k+2$和$k \geqslant 5$。在文章中，假设G是n阶连通图并且在n ≥k + 2和k ≥ 5限制下，可得当$\rho\left(G^{c}\right)＜\rho\left(\left(G^{*}\right)^{c}\right)$，则G存在支撑k树。
Let G be a simple connected undirected graph without multiple edges and loops. If G has a spanning subgraph that is a tree T, and for any vertex v ∈ V(T), it holds that $d_{T}(v) \leqslant k$, then it is called that G exists a spanning k tree. Let A(G) be the adjacency matrix of G, and the adjacency matrix of $G^{c} \text { is } A\left(G^{c}\right)=J_{n}-I_{n}-A(G)$. $\rho\left(G^{c}\right)$ is called the largest eigenvalue of $A\left(G^{c}\right)$, and then it is also called spectral radius of Gc. In this paper, It is assumed that G is a connected graph of order n and that n ≥k + 2 and k ≥ 5 are defined. If $\rho\left(G^{c}\right)＜\rho\left(\left(G^{*}\right)^{c}\right)$, then G exists a spanning k-tree, where $G^{*} \cong K_{1} \vee\left(K_{n-k-1} \cup k K_{1}\right)$.
| [1] |
|
| [2] |
|
| [3] |
|
| [4] |
|
| [5] |
|
| [6] |
|
| [7] |
|
| [8] |
|
| [9] |
|
| [10] |
|
| [11] |
|
| [12] |
|
| [13] |
|
/
| 〈 |
|
〉 |
京公网安备11010202008535号
PDF
(432KB)
