4
$\begingroup$

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.


Definition:

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)

$\endgroup$
0

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.