Spanning trees of K₁,4-free graphs with a bounded number of leaves and branch vertices
In this paper, the author studies the spanning trees with a bounded number of leaves and branch vertices of \(K_{1,4}\)-free graphs. For each positive integer \(p\), let \(\sigma_{p}(G)=\infty\) if \(\alpha(G)<p\) and \(\min\{\sum_{i=1}^{p}d_{G}(v_i)\mid \{v_1, \ldots, v_p\} \text{ is an independent set in } G\}\) otherwise, where \(\alpha(G)\) is the independence number of \(G\). The main result is the following: Let \(k\), \(m\) be two non-negative intergers (\(m \leq k +1\)) and let \(G\) be a connected \(K_{1,4}\)-free graph of order \(n\). If \(\sigma_{m+2}(G) \geq n - k\), then \(G\) has a spanning tree with at most \(m + k + 2\) leaves and branch vertices.\N\NApplying the main results, he also gives some improvements of previous results on the spanning tree with few branch vertices for the case of \(K_{1,4}\)-free graphs.
- A note on the independence number, connectivity and \(k\)-ended tree
- Connected graph \(G\) with \(\sigma_2(G) \geq \frac{2}{3} n\) and \(K_{1, 4}\)-free contains a Hamiltonian path
- Degree conditions for graphs to have spanning trees with few branch vertices and leaves
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 3349867 (Why is no real title available?)
- Independence trees and Hamilton cycles
- Neighborhood unions and extremal spanning trees
- On a conjecture of Las Vergnas concerning certain spanning trees in graphs
- On spanning trees with few branch vertices
- Spanning 3-ended trees in \(k\)-connected \(K_{1,4}\)-free graphs
- Spanning 5-ended trees in \(K_{1,5}\)-free graphs
- Spanning spiders and light-splitting switches
- Spanning trees homeomorphic to a small tree
- Spanning Trees of a Claw-Free Graph Whose Reducible Stems Have Few Leaves
- Spanning trees with a bounded number of branch vertices in a \(K_{1,4}\)-free graph
- Spanning trees with a bounded number of branch vertices in a claw-free graph
- Spanning trees with a bounded number of leaves in a claw-free graph.
- Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs
- Spanning trees with at most 4 leaves in \(K_{1, 5}\)-free graphs
- Spanning trees with at most \(k\) leaves in 2-connected \(K_{1 , r}\)-free graphs
- Spanning trees with at most \(k\) leaves in \(K_{1,4}\)-free graphs
This page was built for publication: Spanning trees of \(K_{1,4}\)-free graphs with a bounded number of leaves and branch vertices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6964826)
