On $\gamma$-labeling the almost-bipartite graph $P_m+e$

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}$ 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 a path with at least $3$ edges by adding an edge joining distinct vertices of the path an even distance apart has a $\gamma$-labeling.