{
  "id": "1905.13292",
  "version": "v1",
  "published": "2019-05-30T20:36:47.000Z",
  "updated": "2019-05-30T20:36:47.000Z",
  "title": "Spanning Trees and Domination in Hypercubes",
  "authors": [
    "Jerrold R. Griggs"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $L(G)$ denote the maximum number of leaves in any spanning tree of a connected graph $G$. We show the (known) result that for the $n$-cube $Q_n$, $L(Q_n) \\sim 2^n = |V(Q_n)|$ as $n\\rightarrow \\infty$. Examining this more carefully, consider the minimum size of a connected dominating set of vertices $\\gamma_c(Q_n)$, which is $2^n-L(Q_n)$ for $n\\ge2$. We show that $\\gamma_c(Q_n)\\sim 2^n/n$. We use Hamming codes and an \"expansion\" method to construct leafy spanning trees in $Q_n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-30T20:36:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "hypercubes",
      "domination",
      "construct leafy spanning trees",
      "maximum number",
      "hamming codes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}