The \(r\)-matching sequencibility of complete graphs (Q1691100)

Summary: In [Bull. Inst. Comb. Appl. 52, 7--20 (2008; Zbl 1157.05035)], \textit{B. Alspach} defined the maximal matching sequencibility of a graph \(G\), denoted \(\mathrm{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 \(\mathrm{ms}(K_n) = \bigl\lfloor\frac{n-1}{2}\bigr\rfloor\). In [Australas. J. Comb. 53, 245--256 (2012; Zbl 1256.05195)], \textit{R. A. Brualdi} et al. extended the definition to cyclic matching sequencibility of a graph \(G\), denoted \(\mathrm{cms}(G)\), which allows cyclical orderings and proved that \(\mathrm{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 \(\mathrm{ms}_r(G)\) and \(\mathrm{cms}_r(G)\) for the non-cyclic and cyclic cases, respectively. We conjecture that \(\mathrm{ms}_r(K_n) = \bigl\lfloor\frac{rn-1}{2}\bigr\rfloor\) and \({\bigl\lfloor\frac{rn-1}{2}\bigr\rfloor-1}\leq \mathrm{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 \(\mathrm{ms}_r(G)\) and \(\mathrm{cms}_r(G)\) as well as results on hypergraph analogues of \(\mathrm{ms}_r(G)\) and \(\mathrm{cms}_r(G)\).