{
  "id": "0705.1806",
  "version": "v1",
  "published": "2007-05-13T01:10:38.000Z",
  "updated": "2007-05-13T01:10:38.000Z",
  "title": "Transversals in trees",
  "authors": [
    "Victor Campos",
    "Vasek Chvatal",
    "Luc Devroye",
    "Perouz Taslakian"
  ],
  "journal": "Journal of Graph Theory 73 (2013), 32 -- 43",
  "categories": [
    "math.CO"
  ],
  "abstract": "A transversal in a rooted tree is any set of nodes that meets every path from the root to a leaf. We let c(T,k) denote the number of transversals of size k in a rooted tree T. We define a partial order on the set of all rooted trees with n nodes by saying that a tree T succeeds a tree T' if c(T,k) is at least c(T',k) for all k and strictly greater than c(T',k) for at least one k. We prove that, for every choice of positive integers d and n, the set of all rooted trees on n nodes where each node has at most d children has a unique minimal element with respect to this partial order and we describe this tree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-05-13T01:10:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C05"
    ],
    "keywords": [
      "rooted tree",
      "transversal",
      "partial order",
      "unique minimal element",
      "strictly greater"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0705.1806C"
    }
  }
}