Remarks on upper and lower bounds for matching sequencibility of graphs

Abstract

In 2008, Alspach [The Wonderful Walecki Construction, Bull. Inst. Combin. Appl. 52 (2008) 7–20] defined the matching sequencibility of a graph $G$ to be the largest integer $k$ such that there exists a linear ordering of its edges so that every $k$ consecutive edges in the linear ordering form a matching of $G$, which is denoted by $ms(G)$. In this paper, we show that every graph $G$ of size $q$ and maximum degree $\Delta$ satisfies $\frac{1}{2}\lfloor \frac{q}{\Delta+1} \rfloor \leq ms(G) \leq \lfloor \frac{q-1}{\Delta-1}$ by using the edge-coloring of $G$, and we also improve this lower bound for some particular graphs.

We further discuss the relationship between the matching sequencibility and a conjecture of Seymour about the existence of the $k$th power of a Hamilton cycle.