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 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 ) ≠ ∅ . For each leaf x of T , let y x denote the nearest branch vertex to x . We delete V ( P T [ x , y x ] ) ∖ { y x } from T for all x ∈ L ( T ) . The resulting subtree of T is called the reducible stem of T and denoted by R 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.

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 k -connected K 1 , 4 -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 K 1 , 5 -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 K 1 , t -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 k 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 K 1 , 4 -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 k leaves in K 1 , 4 -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 K 1 , 3 -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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.