Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2507.04400 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912492448382976 |
|---|---|
| author | Ao, Guoyan Liu, Ruifang Yuan, Jinjiang |
| author_facet | Ao, Guoyan Liu, Ruifang Yuan, Jinjiang |
| contents | Chvátal and Erdös [Discrete Math. 2 (1972) 111-113] stated that, for an $m$-connected graph $G$, if its independence number $α(G)\leq m-1$, then $G$ is Hamilton-connected. Note that $k$-leaf-connectedness is a natural generalization of Hamilton-connectedness of a graph. Ozeki and Yamashita [Graphs Combin. 27 (2011) 1-26] posed an open problem: What is the sufficient condition based on the independence number for an $m$-connected graph to be $k$-leaf-connected? In this paper, we prove that if $α(G)\leq m-k+1,$ then an $m$-connected graph $G$ is $k$-leaf-connected. This not only answers the open problem of Ozeki and Yamashita, but also extends Chvátal-Erdös Theorem. As applications, we present sufficient spectral conditions for an $m$-connected graph to be $k$-leaf-connected.
Let $k\geq 2$ be an integer and $T$ be a spanning tree of a connected graph. The total $k$-excess $te(T,k)$ is the summation of the $k$-excesses of all vertices in $T$, namely, $te(T,k)=\sum_{v\in V(T)}\mbox{max}\{0, d_{T}(v)-k\}.$ One can see that $T$ is a spanning $k$-tree if and only if $te(T,k)=0$. Fan, Goryainov, Huang and Lin [Linear Multilinear Algebra 70 (2022) 7264-7275] presented sufficient spectral conditions for a connected graph to contain a spanning $k$-tree. We in this paper propose sufficient conditions in terms of the spectral radius for a connected graph to contain a spanning tree with $te(T,k)\leq b$, where $b\geq0$ is an integer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04400 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sufficient conditions of $k$-leaf-connected graphs and spanning trees with bounded total $k$-excess Ao, Guoyan Liu, Ruifang Yuan, Jinjiang Spectral Theory Chvátal and Erdös [Discrete Math. 2 (1972) 111-113] stated that, for an $m$-connected graph $G$, if its independence number $α(G)\leq m-1$, then $G$ is Hamilton-connected. Note that $k$-leaf-connectedness is a natural generalization of Hamilton-connectedness of a graph. Ozeki and Yamashita [Graphs Combin. 27 (2011) 1-26] posed an open problem: What is the sufficient condition based on the independence number for an $m$-connected graph to be $k$-leaf-connected? In this paper, we prove that if $α(G)\leq m-k+1,$ then an $m$-connected graph $G$ is $k$-leaf-connected. This not only answers the open problem of Ozeki and Yamashita, but also extends Chvátal-Erdös Theorem. As applications, we present sufficient spectral conditions for an $m$-connected graph to be $k$-leaf-connected. Let $k\geq 2$ be an integer and $T$ be a spanning tree of a connected graph. The total $k$-excess $te(T,k)$ is the summation of the $k$-excesses of all vertices in $T$, namely, $te(T,k)=\sum_{v\in V(T)}\mbox{max}\{0, d_{T}(v)-k\}.$ One can see that $T$ is a spanning $k$-tree if and only if $te(T,k)=0$. Fan, Goryainov, Huang and Lin [Linear Multilinear Algebra 70 (2022) 7264-7275] presented sufficient spectral conditions for a connected graph to contain a spanning $k$-tree. We in this paper propose sufficient conditions in terms of the spectral radius for a connected graph to contain a spanning tree with $te(T,k)\leq b$, where $b\geq0$ is an integer. |
| title | Sufficient conditions of $k$-leaf-connected graphs and spanning trees with bounded total $k$-excess |
| topic | Spectral Theory |
| url | https://arxiv.org/abs/2507.04400 |