Loading...
Please wait, while we are loading the content...
Similar Documents
On large $k$-ended trees in connected graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Nikoghosyan, Zh. G. |
| Copyright Year | 2014 |
| Abstract | A vertex of degree one is called an end-vertex, and an end-vertex of a tree is called a leaf. A tree with at most $k$ leaves is called a $k$-ended tree. For a positive integer $k$, let $t_k$ be the order of a largest $k$-ended tree. Let $\sigma_m$ be the minimum degree sum of an independent set of $m$ vertices. The main result (Theorem 2) provides a lower bound for $t_{k+1}$ in terms of $\sigma_m$ and relative orders: if $G$ is a connected graph and $k$, $\lambda$, $m$ are positive integers with $2\le m\le\min\{k,\lambda\}+1$ then either $t_{k+1} \ge \sigma_m +\lambda(k-m+1)+1$ or $t_k\ge t_{k+1}-\lambda+1$. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/1409.3159v7.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
