| Title:
|
Spanning trees whose reducible stems have a few branch vertices (English) |
| Author:
|
Ha, Pham Hoang |
| Author:
|
Hanh, Dang Dinh |
| Author:
|
Loan, Nguyen Thanh |
| Author:
|
Pham, Ngoc Diep |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
71 |
| Issue:
|
3 |
| Year:
|
2021 |
| Pages:
|
697-708 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
spanning tree |
| Keyword:
|
independence number |
| Keyword:
|
degree sum |
| Keyword:
|
reducible stem |
| MSC:
|
05C05 |
| MSC:
|
05C07 |
| MSC:
|
05C69 |
| idZBL:
|
07396192 |
| idMR:
|
MR4295240 |
| DOI:
|
10.21136/CMJ.2021.0073-20 |
| . |
| Date available:
|
2021-08-02T08:03:52Z |
| Last updated:
|
2023-10-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149051 |
| . |
| Reference:
|
[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 . Zbl 0919.05017, MR 1653817, 10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W |
| Reference:
|
[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 . Zbl 1299.05034, MR 3229223 |
| Reference:
|
[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 . Zbl 1418.05050, MR 3954055 |
| Reference:
|
[4] Diestel, R.: Graph Theory.Graduate Texts in Mathematics 173. Springer, Berlin (2005),\99999DOI99999 10.1007/978-3-662-53622-3 . Zbl 1074.05001, MR 2159259 |
| Reference:
|
[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 . Zbl 1437.05044, MR 4089649 |
| Reference:
|
[6] Ha, P. H., Hanh, D. D., Loan, N. T.: Spanning trees with few peripheral branch vertices.Taiwanese J. Math. 25 (2021), 435-447. 10.11650/tjm/201201 |
| Reference:
|
[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 . Zbl 1265.05100, MR 2907328 |
| Reference:
|
[8] Kano, M., Yan, Z.: Spanning trees whose stems have at most $k$ leaves.Ars Combin. 117 (2014), 417-424 \99999MR99999 3243859 . Zbl 1349.05056, MR 3243859 |
| Reference:
|
[9] Kano, M., Yan, Z.: Spanning trees whose stems are spiders.Graphs Comb. 31 (2015), 1883-1887 \99999DOI99999 10.1007/s00373-015-1618-2 . Zbl 1330.05041, MR 3417201 |
| Reference:
|
[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 . Zbl 1183.05019, MR 2552650 |
| Reference:
|
[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 . Zbl 1235.05033, MR 2825657 |
| Reference:
|
[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. Zbl 0221.05053, MR 0277423 |
| Reference:
|
[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 . Zbl 1407.05053, MR 3898387 |
| Reference:
|
[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 . Zbl 0536.05047, MR 0732027 |
| Reference:
|
[15] Ozeki, K., Yamashita, T.: Spanning trees: A survey.Graphs Comb. 27 (2011), 1-26 \99999DOI99999 10.1007/s00373-010-0973-2 . Zbl 1232.05055, MR 2746831 |
| Reference:
|
[16] Tsugaki, M., Zhang, Y.: Spanning trees whose stems have a few leaves.Ars Comb. 114 (2014), 245-256. Zbl 1324.05025, MR 3203267 |
| Reference:
|
[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 . Zbl 0432.05035, MR 0565381 |
| Reference:
|
[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 . Zbl 1339.05212, MR 3518139 |
| . |
