Rooted induced trees in triangle-free graphs

Publication date 10 November 2010

Abstract: For a graph

G

, let

t (G)

denote the maximum number of vertices in an induced subgraph of

G

that is a tree. Further, for a vertex

v i n V (G)

, let

t^{v} (G)

denote the maximum number of vertices in an induced subgraph of

G

that is a tree, with the extra condition that the tree must contain

v

. The minimum of

t (G)

(

t^{v} (G)

, respectively) over all connected triangle-free graphs

G

(and vertices

v i n V (G)

) on

n

vertices is denoted by

t_{3} (n)

(

t_{3}^{v} (n)

). Clearly,

t^{v} (G) l e t (G)

for all

v i n V (G)

. In this note, we solve the extremal problem of maximizing

| G |

for given

t^{v} (G)

, given that

G

is connected and triangle-free. We show that

| G | l e 1 + f r a c (t_{v} (G) - 1) t_{v} (G) 2

and determine the unique extremal graphs. Thus, we get as corollary that

t_{3} (n) g e t_{3}^{v} (n) = l c e i l 1 / 2 (1 + s q r t 8 n - 7) c e i l

, improving a recent result by Fox, Loh and Sudakov.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Rooted induced trees in triangle-free graphs