On \(\gamma\)-Labeling of the Almost-Bipartite Graph \((P_{m}\Box P_{n})+\hat{e}\)

In 2004, Blinco et al [1] introduced \(\gamma\)-labeling. A function \(h\) defined on the vertex set of a graph \(G\) with \(n\) edges is called a \(\gamma\)-labeling if:

1. \(h\) is a \(p\)-labeling of \(G\),
2. \(G\) admits a tripartition \((A, B, C)\) with \(C = \{c\}\) and there exists \(\overline{b} \in B\) such that \((\overline{b}, c)\) is the unique edge with the property that \(h(c) – h(\overline{b}) = n\),
3. for every edge \(\{a, v\} \in E(G)\) with \(a \in A\), \(h(a) < h(v)\).

In [1] they have also proved a significant result on graph decomposition that if a graph \(G\) with \(n\) edges admits a \(\gamma\)-labeling then the complete graph \(K_{2cn+1}\) can be cyclically decomposed into \(2cn + 1\) copies of the graph \(G\), where \(c\) is any positive integer.

Motivated by the result of Blinco et al [1], in this paper, we prove that the well-known almost-bipartite graph, the grid with an additional edge, \((P_m \Box P_n) + \hat{e}\), admits \(\gamma\)-labeling. Further, we discuss a related open problem.