Spanning trees whose reducible stems have a few branch vertices

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

Czechoslovak Mathematical Journal, Tome 71 (2021) no. 3, pp. 697-708.

Résumé

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.

Détail

DOI : 10.21136/CMJ.2021.0073-20

Classification : 05C05, 05C07, 05C69
Keywords: spanning tree; independence number; degree sum; reducible stem