Spanning trees whose reducible stems have a few branch vertices

Pham Hoang Ha; Dang Dinh Hanh; Nguyen Thanh Loan; Ngoc Diep Pham

Czechoslovak Mathematical Journal (2021)

  • Volume: 71, Issue: 3, page 697-708
  • ISSN: 0011-4642

Abstract

top
Let be a tree. Then a vertex of with degree one is a leaf of and a vertex of degree at least three is a branch vertex of . The set of leaves of is denoted by and the set of branch vertices of is denoted by . For two distinct vertices , of , let denote the unique path in connecting and Let be a tree with . For each leaf of , let denote the nearest branch vertex to . We delete from for all . The resulting subtree of is called the reducible stem of and denoted by . 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.

How to cite

top

Ha, Pham Hoang, et al. "Spanning trees whose reducible stems have a few branch vertices." Czechoslovak Mathematical Journal 71.3 (2021): 697-708. <http://eudml.org/doc/297701>.

@article{Ha2021,
abstract = {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) \ne \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 \lbrace y_x\rbrace $ 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.},
author = {Ha, Pham Hoang, Hanh, Dang Dinh, Loan, Nguyen Thanh, Pham, Ngoc Diep},
journal = {Czechoslovak Mathematical Journal},
keywords = {spanning tree; independence number; degree sum; reducible stem},
language = {eng},
number = {3},
pages = {697-708},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Spanning trees whose reducible stems have a few branch vertices},
url = {http://eudml.org/doc/297701},
volume = {71},
year = {2021},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 71
IS - 3
SP - 697
EP - 708
AB - 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) \ne \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 \lbrace y_x\rbrace $ 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.
LA - eng
KW - spanning tree; independence number; degree sum; reducible stem
UR - http://eudml.org/doc/297701
ER -

References

top
  1. Broersma, H., Tuinstra, H., 10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W, J. Graph Theory 29 (1998), 227-237 9999DOI99999 10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W . (1998) Zbl0919.05017MR1653817DOI10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W
  2. Chen, Y., Chen, G., Hu, Z., Spanning 3-ended trees in -connected -free graphs, Sci. China, Math. 57 (2014), 1579-1586 9999DOI99999 10.1007/s11425-014-4817-z . (2014) Zbl1299.05034MR3229223
  3. Chen, Y., Ha, P. H., Hanh, D. D., Spanning trees with at most 4 leaves in -free graphs, Discrete Math. 342 (2019), 2342-2349 9999DOI99999 10.1016/j.disc.2019.05.005 . (2019) Zbl1418.05050MR3954055
  4. Diestel, R., Graph Theory, Graduate Texts in Mathematics 173. Springer, Berlin (2005),9999DOI99999 10.1007/978-3-662-53622-3 . (2005) Zbl1074.05001MR2159259
  5. Ha, P. H., Hanh, D. D., Spanning trees of connected -free graphs whose stems have a few leaves, Bull. Malays. Math. Sci. Soc. (2) 43 (2020), 2373-2383 9999DOI99999 10.1007/s40840-019-00812-x . (2020) Zbl1437.05044MR4089649
  6. Ha, P. H., Hanh, D. D., Loan, N. T., 10.11650/tjm/201201, Taiwanese J. Math. 25 (2021), 435-447. (2021) DOI10.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 9999MR99999 2907328 . (2012) Zbl1265.05100MR2907328
  8. Kano, M., Yan, Z., Spanning trees whose stems have at most leaves, Ars Combin. 117 (2014), 417-424 9999MR99999 3243859 . (2014) Zbl1349.05056MR3243859
  9. Kano, M., Yan, Z., Spanning trees whose stems are spiders, Graphs Comb. 31 (2015), 1883-1887 9999DOI99999 10.1007/s00373-015-1618-2 . (2015) Zbl1330.05041MR3417201
  10. Kyaw, A., Spanning trees with at most 3 leaves in -free graphs, Discrete Math. 309 (2009), 6146-6148 9999DOI99999 10.1016/j.disc.2009.04.023 . (2009) Zbl1183.05019MR2552650
  11. Kyaw, A., Spanning trees with at most leaves in -free graphs, Discrete Math. 311 (2011), 2135-2142 9999DOI99999 10.1016/j.disc.2011.06.025 . (2011) Zbl1235.05033MR2825657
  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. (1971) Zbl0221.05053MR0277423
  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 9999DOI99999 10.1007/s00373-018-1998-1 . (2019) Zbl1407.05053MR3898387
  14. Matthews, M. M., Sumner, D. P., Hamiltonian results in -free graphs, J. Graph Theory 8 (1984), 139-146 9999DOI99999 10.1002/jgt.3190080116 . (1984) Zbl0536.05047MR0732027
  15. Ozeki, K., Yamashita, T., Spanning trees: A survey, Graphs Comb. 27 (2011), 1-26 9999DOI99999 10.1007/s00373-010-0973-2 . (2011) Zbl1232.05055MR2746831
  16. Tsugaki, M., Zhang, Y., Spanning trees whose stems have a few leaves, Ars Comb. 114 (2014), 245-256. (2014) Zbl1324.05025MR3203267
  17. Win, S., On a conjecture of Las Vergnas concerning certain spanning trees in graphs, Result. Math. 2 (1979), 215-224 9999DOI99999 10.1007/BF03322958 . (1979) Zbl0432.05035MR0565381
  18. Yan, Z., Spanning trees whose stems have a bounded number of branch vertices, Discuss. Math., Graph Theory 36 (2016), 773-778 9999DOI99999 10.7151/dmgt.1885 . (2016) Zbl1339.05212MR3518139

NotesEmbed ?

top

You must be logged in to post comments.