Rooted induced trees in triangle-free graphs - Mathematics > CombinatoricsReport as inadecuate




Rooted induced trees in triangle-free graphs - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: For a graph $G$, let $tG$ denote the maximum number of vertices in aninduced subgraph of $G$ that is a tree. Further, for a vertex $v\in VG$, let$t^vG$ 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$. Theminimum of $tG$ $t^vG$, respectively over all connected triangle-freegraphs $G$ and vertices $v\in VG$ on $n$ vertices is denoted by $t 3n$$t 3^vn$. Clearly, $t^vG\le tG$ for all $v\in VG$. In this note, wesolve the extremal problem of maximizing $|G|$ for given $t^vG$, given that$G$ is connected and triangle-free. We show that $|G|\le1+\frac{t vG-1t vG}{2}$ and determine the unique extremal graphs. Thus,we get as corollary that $t 3n\ge t 3^vn=\lceil{1-2}1+\sqrt{8n-7} ceil$, improving a recent result by Fox, Loh and Sudakov.



Author: Florian Pfender

Source: https://arxiv.org/



DOWNLOAD PDF




Related documents