Geodesic
Spanning trees whose reducible stems have a few branch vertices
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 3, pp. 697-708
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2021.0073-20
Classification : 05C05, 05C07, 05C69
Keywords: spanning tree; independence number; degree sum; reducible stem 
@article{10_21136_CMJ_2021_0073_20,
     author = {Ha, Pham Hoang and Hanh, Dang Dinh and Loan, Nguyen Thanh and Pham, Ngoc Diep},
     title = {Spanning trees whose reducible stems have a few branch vertices},
     journal = {Czechoslovak Mathematical Journal},
     pages = {697--708},
     year = {2021},
     volume = {71},
     number = {3},
     doi = {10.21136/CMJ.2021.0073-20},
     mrnumber = {4295240},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0073-20/}
}
TY  - JOUR
AU  - Ha, Pham Hoang
AU  - Hanh, Dang Dinh
AU  - Loan, Nguyen Thanh
AU  - Pham, Ngoc Diep
TI  - Spanning trees whose reducible stems have a few branch vertices
JO  - Czechoslovak Mathematical Journal
PY  - 2021
SP  - 697
EP  - 708
VL  - 71
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0073-20/
DO  - 10.21136/CMJ.2021.0073-20
LA  - en
ID  - 10_21136_CMJ_2021_0073_20
ER  - 
%0 Journal Article
%A Ha, Pham Hoang
%A Hanh, Dang Dinh
%A Loan, Nguyen Thanh
%A Pham, Ngoc Diep
%T Spanning trees whose reducible stems have a few branch vertices
%J Czechoslovak Mathematical Journal
%D 2021
%P 697-708
%V 71
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0073-20/
%R 10.21136/CMJ.2021.0073-20
%G en
%F 10_21136_CMJ_2021_0073_20
Ha, Pham Hoang; Hanh, Dang Dinh; Loan, Nguyen Thanh; Pham, Ngoc Diep. Spanning trees whose reducible stems have a few branch vertices. Czechoslovak Mathematical Journal, Tome 71 (2021) no. 3, pp. 697-708. doi: 10.21136/CMJ.2021.0073-20

[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 | MR | JFM

[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 | JFM

[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 | JFM

[4] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173. Springer, Berlin (2005),\99999DOI99999 10.1007/978-3-662-53622-3 . | MR | JFM

[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 | JFM

[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

[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 | JFM

[8] Kano, M., Yan, Z.: Spanning trees whose stems have at most $k$ leaves. Ars Combin. 117 (2014), 417-424 \99999MR99999 3243859 . | MR | JFM

[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 | JFM

[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 | JFM

[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 | JFM

[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 | JFM

[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 | JFM

[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 | JFM

[15] Ozeki, K., Yamashita, T.: Spanning trees: A survey. Graphs Comb. 27 (2011), 1-26 \99999DOI99999 10.1007/s00373-010-0973-2 . | MR | JFM

[16] Tsugaki, M., Zhang, Y.: Spanning trees whose stems have a few leaves. Ars Comb. 114 (2014), 245-256. | MR | JFM

[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 | JFM

[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 | JFM

Cité par Sources :