TY - JOUR

T1 - Construction of Antimagic Labeling for the Cartesian Product of Regular Graphs

AU - Phanalasy, Oudone

AU - Miller, Mirka

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Vaezpour, Elaheh

PY - 2011/3/1

Y1 - 2011/3/1

N2 - An antimagic labeling of a graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1, 2, . . ., q} such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. A graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that that every connected graph, except K2, is antimagic. Recently, using completely separating systems, Phanalasy et al. showed that for each k ≥ 2, q ≥(k+12) with k{pipe}2q, there exists an antimagic k-regular graph with q edges and p = 2q/k vertices. In this paper we prove constructively that certain families of Cartesian products of regular graphs are antimagic.

AB - An antimagic labeling of a graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1, 2, . . ., q} such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. A graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that that every connected graph, except K2, is antimagic. Recently, using completely separating systems, Phanalasy et al. showed that for each k ≥ 2, q ≥(k+12) with k{pipe}2q, there exists an antimagic k-regular graph with q edges and p = 2q/k vertices. In this paper we prove constructively that certain families of Cartesian products of regular graphs are antimagic.

KW - Antimagic graph labeling

KW - Cartesian product of graphs

KW - Completely separating systems

KW - Regular graph

UR - http://www.scopus.com/inward/record.url?scp=81955167487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=81955167487&partnerID=8YFLogxK

U2 - 10.1007/s11786-011-0084-3

DO - 10.1007/s11786-011-0084-3

M3 - Article

AN - SCOPUS:81955167487

VL - 5

SP - 81

EP - 87

JO - Mathematics in Computer Science

JF - Mathematics in Computer Science

SN - 1661-8270

IS - 1

ER -