ONγ-LABELING THE ALMOST-BIPARTITE GRAPH Km,n + e

S. I. El-Zanati; W. A. O’Hanlon; E. R. Spicer

S. I. El-Zanati
W. A. O’Hanlon
E. R. Spicer

Keywords: G-design, almost-bipartite graph,γ-labeling.

Abstract

Let G be a graph with n edges and let k be a positive integer. A G-design of order k is a G-decomposition of Kk.Alabeling of G is an assignment of non-negative integers to the vertices of G. Some labelings of such a G lead to cyclic G-designs of order 2nx+1. Until recently, such labelings were restricted to bipartite graphs only. 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-designs of order 2nx+1 was recently introduced by Blinco, El-Zanati, and Vanden Eynden. They called such a labeling a γ-labeling. In this note, we survey almost-bipartite graphs that admit γ-labelings and ﬁnd necessary and suﬃcient conditions for a γ-labeling of Km,n + e.