Rooted induced trees in triangle-free graphs
| dc.creator | Pfender, Florian | |
| dc.date | 2008-04-09 | |
| dc.date | 2008-12-15 | |
| dc.date.accessioned | 2026-07-07T12:12:16Z | |
| dc.date.available | 2026-07-07T12:12:16Z | |
| dc.description | 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. | |
| dc.description | 2 pages, minor edits for better readability | |
| dc.identifier | https://arxiv.org/abs/0804.1535 | |
| dc.identifier | http://arxiv.org/abs/0804.1535 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/210489 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35 | |
| dc.title | Rooted induced trees in triangle-free graphs | |
| dc.type | text |