Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
spanning tree; independence number; degree sum; reducible stem
spanning tree; independence number; degree sum; reducible stem
Summary:
Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$. The set of leaves of $T$ is denoted by $L(T)$ and the set of branch vertices of $T$ is denoted by $B(T)$. For two distinct vertices $u$, $v$ of $T$, let $P_T[u,v]$ denote the unique path in $T$ connecting $u$ and $v.$ Let $T$ be a tree with $B(T) \neq \emptyset $. For each leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. We delete $V(P_T[x,y_x])\setminus \{y_x\}$ from $T$ for all $x \in L(T)$. The resulting subtree of $T$ is called the reducible stem of $T$ and denoted by ${\rm R}_{\rm Stem}(T)$. We give sharp sufficient conditions on the degree sum for a graph to have a spanning tree whose reducible stem has a few branch vertices.
References:
[1] Broersma, H., Tuinstra, H.: Independence trees and Hamilton cycles. J. Graph Theory 29 (1998), 227-237 \99999DOI99999 10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W . DOI 10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W | MR 1653817 | Zbl 0919.05017
[2] Chen, Y., Chen, G., Hu, Z.: Spanning 3-ended trees in $k$-connected $K_{1,4}$-free graphs. Sci. China, Math. 57 (2014), 1579-1586 \99999DOI99999 10.1007/s11425-014-4817-z . MR 3229223 | Zbl 1299.05034
[3] Chen, Y., Ha, P. H., Hanh, D. D.: Spanning trees with at most 4 leaves in $K_{1,5}$-free graphs. Discrete Math. 342 (2019), 2342-2349 \99999DOI99999 10.1016/j.disc.2019.05.005 . MR 3954055 | Zbl 1418.05050
[4] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173. Springer, Berlin (2005),\99999DOI99999 10.1007/978-3-662-53622-3 . MR 2159259 | Zbl 1074.05001
[5] Ha, P. H., Hanh, D. D.: Spanning trees of connected $K_{1,t}$-free graphs whose stems have a few leaves. Bull. Malays. Math. Sci. Soc. (2) 43 (2020), 2373-2383 \99999DOI99999 10.1007/s40840-019-00812-x . MR 4089649 | Zbl 1437.05044
[6] Ha, P. H., Hanh, D. D., Loan, N. T.: Spanning trees with few peripheral branch vertices. Taiwanese J. Math. 25 (2021), 435-447. DOI 10.11650/tjm/201201
[7] Kano, M., Kyaw, A., Matsuda, H., Ozeki, K., Saito, A., Yamashita, T.: Spanning trees with a bounded number of leaves in a claw-free graph. Ars Combin. 103 (2012), 137-154 \99999MR99999 2907328 . MR 2907328 | Zbl 1265.05100
[8] Kano, M., Yan, Z.: Spanning trees whose stems have at most $k$ leaves. Ars Combin. 117 (2014), 417-424 \99999MR99999 3243859 . MR 3243859 | Zbl 1349.05056
[9] Kano, M., Yan, Z.: Spanning trees whose stems are spiders. Graphs Comb. 31 (2015), 1883-1887 \99999DOI99999 10.1007/s00373-015-1618-2 . MR 3417201 | Zbl 1330.05041
[10] Kyaw, A.: Spanning trees with at most 3 leaves in $K_{1,4}$-free graphs. Discrete Math. 309 (2009), 6146-6148 \99999DOI99999 10.1016/j.disc.2009.04.023 . MR 2552650 | Zbl 1183.05019
[11] Kyaw, A.: Spanning trees with at most $k$ leaves in $K_{1,4}$-free graphs. Discrete Math. 311 (2011), 2135-2142 \99999DOI99999 10.1016/j.disc.2011.06.025 . MR 2825657 | Zbl 1235.05033
[12] Vergnas, M. Las: Sur une propriété des arbres maximaux dans un graphe. C. R. Acad. Sci., Paris, Sér. A 272 (1971), 1297-1300 French. MR 0277423 | Zbl 0221.05053
[13] Maezawa, S.-i., Matsubara, R., Matsuda, H.: Degree conditions for graphs to have spanning trees with few branch vertices and leaves. Graphs Comb. 35 (2019), 231-238 \99999DOI99999 10.1007/s00373-018-1998-1 . MR 3898387 | Zbl 1407.05053
[14] Matthews, M. M., Sumner, D. P.: Hamiltonian results in $K_{1,3}$-free graphs. J. Graph Theory 8 (1984), 139-146 \99999DOI99999 10.1002/jgt.3190080116 . MR 0732027 | Zbl 0536.05047
[15] Ozeki, K., Yamashita, T.: Spanning trees: A survey. Graphs Comb. 27 (2011), 1-26 \99999DOI99999 10.1007/s00373-010-0973-2 . MR 2746831 | Zbl 1232.05055
[16] Tsugaki, M., Zhang, Y.: Spanning trees whose stems have a few leaves. Ars Comb. 114 (2014), 245-256. MR 3203267 | Zbl 1324.05025
[17] Win, S.: On a conjecture of Las Vergnas concerning certain spanning trees in graphs. Result. Math. 2 (1979), 215-224 \99999DOI99999 10.1007/BF03322958 . MR 0565381 | Zbl 0432.05035
[18] Yan, Z.: Spanning trees whose stems have a bounded number of branch vertices. Discuss. Math., Graph Theory 36 (2016), 773-778 \99999DOI99999 10.7151/dmgt.1885 . MR 3518139 | Zbl 1339.05212
Search
Partner of
