Header menu link for other important links
On γ-labeling of the almost-bipartite graph (Pm□Pn) + ê
G. Sethuraman,
Published in Charles Babbage Research Centre
Volume: 92
Pages: 15 - 24
In 2004, Bunco et al [1] introduced γ-labeling. A function h defined on the vertex set of a graph G with n edges is called γ-labeling if, (i) h is a ρ-labeling of G, (ii) G admits a tripartition (A, B, G) 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, (iii) for every edge (a, v) ∈ E(G) with a ∈ 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 γ-labeling then the complete graph K2cn+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, (Pm□Pn) + ê, admits γ-labeling. Further, we discuss a related open problem.
About the journal
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
PublisherCharles Babbage Research Centre