The $r$-matching sequencibility of complete graphs

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)=\lfloor \frac{n-1}{2}\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)=\lfloor \frac{n-2}{2}\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\ge 1$, and we denote the maximum such number for a graph $G$ by $m{s}_r(G)$ and $cm{s}_r(G)$ for the non-cyclic and cyclic cases, respectively. We conjecture that $m{s}_r(K_n)=\lfloor \frac{rn-1}{2}\rfloor$ and $\lfloor \frac{rn-1}{2}\rfloor -1\le cm{s}_r(K_n)\le \lfloor \frac{rn-1}{2}\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 $m{s}_r(G)$ and $cm{s}_r(G)$ as well as results on hypergraph analogues of $m{s}_r(G)$ and $cm{s}_r(G)$.