On large k-ended trees in connected graphs

Publication date: 10 September 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

s i g m a_{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

s i g m a_{m}

and relative orders: if

G

is a connected graph and

k

,

l a m b d a

,

m

are positive integers with

2 l e m l e m i n k, l a m b d a + 1

then either

t_{k + 1} g e s i g m a_{m} + l a m b d a (k - m + 1) + 1

or

t_{k} g e t_{k + 1} - l a m b d a + 1

.

This page was built for publication: On large $k$-ended trees in connected graphs