Rooted induced trees in triangle-free graphs

Details Rooted induced trees in triangle-free graphs Rooted induced trees in triangle-free graphs

2008-04-09

arxiv.org/abs/0804.1535v2

Mathematics

Combinatorics

2 pages, minor edits for better readability

Scientific paper

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\in 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\in V(G)$) on $n$ vertices is denoted by $t_3(n)$ ($t_3^v(n)$). Clearly, $t^v(G)\le t(G)$ for all $v\in 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|\le 1+\frac{(t_v(G)-1)t_v(G)}{2}$ and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^v(n)=\lceil {1/2}(1+\sqrt{8n-7})\rceil$, improving a recent result by Fox, Loh and Sudakov.

Affiliated with

Also associated with

No associations

Rating

Rooted induced trees in triangle-free graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rooted induced trees in triangle-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rooted induced trees in triangle-free graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-575117