On Free $q$-Labelings of Cubic Bipartite Graphs

Abstract

It is known that an $\alpha$-labeling of a bipartite graph $G$ with $n$ edges can be used to obtain a cyclic $G$-decomposition of $K_{2nx+1}$ for every positive integer $x$. It is also known that if two graphs $G$ and $H$ admit a free $a$-labeling, then their vertex-disjoint union also admits a free $\alpha$-labeling. We show that if $G$ is a bipartite prism, a bipartite Möbius ladder, or a connected cubic bipartite graph of order at most 14, then $G$ admits a free $a$-labeling. We conjecture that every bipartite cubic graph admits a free $\alpha$-labeling.