The graph depicted below, when cyclically rotated, gives a decomposition of $K_{33,33}$. It has $22$ vertices, $33$ edges, and is $3$-regular (i.e., cubic). It was found by my computer.

a $22$-vertex, $33$-edge, cubic graph which gives a decomposition of $K_{33,33}$

We can verify the decomposition claim by checking that each edge length occurs exactly once. It is therefore possible that this decomposition is equivalent to an alpha-labelling (perhaps by multiplying the indices by a number coprime to $33$ and/or adding a constant).

Question: How can I determine if this decomposition of $K_{33,33}$ comes from an alpha-labelling?

And, of course, I'm not just interested in this particular graph, but being able to solve instances of this problem in general.


An alpha-labelling is a labelling $f$ of the vertices of an $n$-edge graph with distinct labels from $\{0,1,\ldots,n\}$ such that (a) if each edge $xy$ is assigned the label $|f(x)-f(y)|$, the resulting edge labels are distinct, and (b) there exists an integer $k$ so that for each edge $xy$ either $f(x) \leq k < f(y)$ or $f(y) \leq k < f(x)$. For example:

alpha labelling of a graph

(with $k=6$; example "borrowed" from Pasotti, Constructions for cyclic Moebius ladder systems, Disc. Math., 2010).

They give rise to decompositions of $K_{n,n}$. The above example gives rise to:

decomposition of $K_{20,20}$

(for each of the $n$ edges, big indices ($> k$) go up the top, and small indices ($\leq k$) down the bottom; taken modulo $n$) which gives a decomposition of $K_{21,21}$ if cycled.

(El-Zanati and Eynden, Decompositions of $K_{m,n}$ into cubes, J. Combin. Des., 1996)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.