Langford sequences from products of labeled digraphs

Susana-C. L\'opez
Universitat Politècnica de Catalunya

Francesc-A. Muntaner-Batle
The University of Newcastle



Content: For $m\le n$, we denote the set $\{m,m+1,\ldots, n\}$ by $[m,n]$. Let $d$ be a positive integer. A {\it Langford sequence} of order $m$ and defect $d$ is a sequence $(l_1,l_2,\ldots, l_{2m})$ of $2m$ numbers such that (i) for every $k\in [d,d+m-1]$ there exist exactly two subscripts $i,j\in [1,2m]$ with $l_i=l_j=k$, (ii) the subscripts $i$ and $j$ satisfy the condition $|i-j|=k$. A Langford sequence of order $m$ and defect $d=1$ is a Skolem sequence of order $m$. Abraham showed that the number of Skolem sequences of order $m$ is at least $ 2^{\lfloor m/3\rfloor}$ for every $m\equiv 0$ or $1$ (mod $4$). We say that a digraph $D$ admits a labeling $f$ if its underlying graph admits the labeling $f$. For any Skolem sequence of order $m$, we define a {\it Skolem labeling} $g$ of the directed matching $m\overrightarrow{K_2}$, up to isomorphism. Let $f:E(m\overrightarrow{K_2})\rightarrow [1,m]$ be any bijective function such that if $f(u,v)=k$, then the Skolem labeling $g$ of $m\overrightarrow{K_2}$ assigns to $u$ one of the two positions occupied by $k$ and to $v$ the other position occupied by $k$, in such a way that the label of $u$ is strictly smaller than the label of $v$. In a similar way, we can define a {\it Langford labeling} of $m\overrightarrow{K_2}$, up to isomorphism, for any Langford sequence of order $m$ and defect $d$. In this talk, we present a study of Skolem and Langford sequences through Skolem and Langford labelings of $m\overrightarrow{K_2}$. By multiplying a Skolem labeled matching $m\overrightarrow{K_2}$ by a particular family of labeled $1$-regular digraphs of order $n$, we obtain a Langford labeled matching $(mn)\overrightarrow{K_2}$. We will show that this procedure can also be applied to obtain Langford sequences from existing ones, and that in this way, we can obtain a lower bound for the number of Langford sequences, for particular values of the defect. We also extend this procedure to hooked and extended Skolem sequences. \noindent{\it 2010 Mathematics subject classification:} 11B99, 05C76 and 05C78. \noindent{\it Key words:} Skolem sequence, Langford sequence, $\otimes_h$-product, super edge-magic labeling. \noindent {\bf Acknowledgements} The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and symbolically by the Catalan Research Council under grant 2014SGR1147.

Back to all abstracts