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.