{
  "id": "0804.1535",
  "version": "v2",
  "published": "2008-04-09T18:30:29.000Z",
  "updated": "2008-12-15T17:24:33.000Z",
  "title": "Rooted induced trees in triangle-free graphs",
  "authors": [
    "Florian Pfender"
  ],
  "comment": "2 pages, minor edits for better readability",
  "categories": [
    "math.CO"
  ],
  "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\\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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-12-15T17:24:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "rooted induced trees",
      "maximum number",
      "unique extremal graphs",
      "induced subgraph",
      "extra condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 2,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0804.1535P"
    }
  }
}