{
  "id": "1711.05013",
  "version": "v1",
  "published": "2017-11-14T09:26:49.000Z",
  "updated": "2017-11-14T09:26:49.000Z",
  "title": "The $r$-matching sequencibility of complete graphs",
  "authors": [
    "Adam Mammoliti"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Alspach [ Bull. Inst. Combin. Appl., 52 (2008), pp. 7-20] defined the maximal matching sequencibility of a graph $G$, denoted $ms(G)$, to be the largest integer $s$ for which there is an ordering of the edges of $G$ such that every $s$ consecutive edges form a matching. Alspach also proved that $ms(K_n) = \\bigl\\lfloor\\frac{n-1}{2}\\bigr\\rfloor$. Brualdi et al. [ Australas. J. Combin., 53 (2012), pp. 245-256] extended the definition to cyclic matching sequencibility of a graph $G$, denoted $cms(G)$, which allows cyclical orderings and proved that $cms(K_n) = \\bigl\\lfloor\\frac{n-2}{2}\\bigr\\rfloor$. In this paper, we generalise these definitions to require that every $s$ consecutive edges form a subgraph where every vertex has degree at most $r\\geq 1$, and we denote the maximum such number for a graph $G$ by $ms_r(G)$ and $cms_r(G)$ for the non-cyclic and cyclic cases, respectively. We conjecture that $ms_r(K_n) = \\bigl\\lfloor\\frac{rn-1}{2}\\bigr\\rfloor$ and ${\\bigl\\lfloor\\frac{rn-1}{2}\\bigr\\rfloor-1}~ \\leq cms_r(K_n) \\leq \\bigl\\lfloor\\frac{rn-1}{2}\\bigr\\rfloor$ and that both bounds are attained for some $r$ and $n$. We prove these conjectured identities for the majority of cases, by defining and characterising selected decompositions of $K_n$. We also provide bounds on $ms_r(G)$ and $cms_r(G)$ as well as results on hypergraph analogues of $ms_r(G)$ and $cms_r(G)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-14T09:26:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65",
      "05C70",
      "05C78"
    ],
    "keywords": [
      "complete graphs",
      "consecutive edges form",
      "cyclic cases",
      "maximal matching sequencibility",
      "cyclic matching sequencibility"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}