Construction of Antimagic Labeling for the Cartesian Product of Regular Graphs

Oudone Phanalasy*, Mirka Miller, Costas S. Iliopoulos, Solon P. Pissis, Elaheh Vaezpour

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)81-87
Number of pages7
JournalMathematics in Computer Science
Volume5
Issue number1
DOIs
Publication statusPublished - 1 Mar 2011
Externally publishedYes

Keywords

  • Antimagic graph labeling
  • Cartesian product of graphs
  • Completely separating systems
  • Regular graph

Fingerprint Dive into the research topics of 'Construction of Antimagic Labeling for the Cartesian Product of Regular Graphs'. Together they form a unique fingerprint.

Cite this