On Cyclic \((C_{2m} + e)\)-Designs

Abstract

An almost-bipartite graph is a non-bipartite graph with the property that the removal of a particular single edge renders the graph bipartite. A graph labeling of an almost-bipartite graph \(G\) with \(n\) edges that yields cyclic \(G\)-decompositions of the complete graph \(K_{2nt+1}\) (i.e., cyclic \((K_{2nt+1}, G)\)-designs) was recently introduced by Blinco, El-Zanati, and Vanden Eynden. They called such a labeling a \(\gamma\)-labeling. Here we show that the class of almost-bipartite graphs obtained from \(C_m\) by adding an edge joining distinct vertices in the same part in the bipartition of \(V(C_{2m})\) has a \(\gamma\)-labeling if and only if \(m \geq 3\). This, along with results of Blinco and of Froncek, shows that if \(G\) is a graph of size \(n\) consisting of a cycle with a chord, then there exists a cyclic \((K_{2nt+1},G)\)-design for every positive integer \(t\).