Stars on trees

Abstract: For a positive integer

r

and a vertex

v

of a graph

G

, let

m a t h c a l I_{G}^{(r)} (v)

denote the set of all independent sets of

G

that have exactly

r

elements and contain

v

. Hurlbert and Kamat conjectured that for any

r

and any tree

T

, there exists a leaf

z

of

T

such that

| m a t h c a l I_{T}^{(r)} (v) | l e q | m a t h c a l I_{T}^{(r)} (z) |

for each vertex

v

of

T

. They proved the conjecture for

r l e q 4

. For any

k g e q 3

, we construct a tree

T_{k}

that has a vertex

x

such that

x

is not a leaf of

T_{k}

,

| m a t h c a l I_{T_{k}}^{(r)} (z) | < | m a t h c a l I_{T_{k}}^{(r)} (x) |

for any leaf

z

of

T_{k}

and any

5 l e q r l e q 2 k + 1

, and

2 k + 1

is the largest integer

s

for which

m a t h c a l I_{T_{k}}^{(s)} (x)

is non-empty. Therefore, the conjecture is not true for

r g e q 5

.

Recommendations

Cites Work

Cited In (11)

This page was built for publication: Stars on trees