On γ-Labeling of the Almost-Bipartite Graph (P_m□P_n) + e

摘要

In 2004, Blinco et al introduced γ-labeling. A function h defined on the vertex set of a graph G with n edges is called γ-labeling if, (ⅰ) h is a ρ-labeling of G, (ⅱ) G admits a tripartition (A, B, C) with C = {c} and there exist b ∈ B such that (b, c) is the unique edge with the property that h(c) - h(b) = n, (ⅲ) for every edge (a,v) ∈ E(G) with a ∈ A, h(a) ＜ h(v). In they have also proved a significant result on graph decomposition that if a graph G with n edges admits a γ-labeling then the complete graph K_(acn+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, in this paper we prove that the well known almost-bipartite graph, the grid with an additional edge, (P_m□P_n) + e, admits γ-labeling. Further, we discuss a related open problem.