Paper Info
Title
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) = bigllfloorfrac{n-1}{2}bigrrfloor$. 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) = bigllfloorfrac{n-2}{2}bigrrfloor$. In this paper, we generalise these definitions to require that every $s$ consecutive edges form a subgraph where every vertex has degree at most $rgeq 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) = bigllfloorfrac{rn-1}{2}bigrrfloor$ and ${bigllfloorfrac{rn-1}{2}bigrrfloor-1} leq cms_r(K_n)  leq  bigllfloorfrac{rn-1}{2}bigrrfloor$ 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)$.
Year
Venue
Field
2018
Electr. J. Comb.
Discrete mathematics,Combinatorics,Vertex (geometry),Robertson–Seymour theorem,Partial k-tree,Hypergraph,1-planar graph,Mathematics,Pancyclic graph,Metric dimension,Trapezoid graph
DocType
Volume
Issue
Journal
25
1
ISSN
Citations 
PageRank 
Adam Mammoliti, The r-matching sequencibility of complete graphs, Electron. J. Combin. 25 (2018), Paper 1.6, 23 pp
0
0.34
References 
Authors
1
1
Name
Order
Citations
PageRank
Adam Mammoliti101.35