Another Antimagic Conjecture

Abstract

An antimagic labeling of a graph G is a bijection f : E(G) → {1, . . . , |E(G)|} such that the weights w(x) = ∑y∼x f(y) distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1990) is that every connected graph other than K2 admits an antimagic labeling. For a set of distances D, a D-antimagic labeling of a graph G is a bijection f : V(G) → {1, . . . , |V(G)|} such that the weight ω(x) = ∑y∈ND(x) f(y) is distinct for each vertex x, where ND(x) = {y ∈ V(G)|d(x, y) ∈ D} is the D-neigbourhood set of a vertex x. If ND(x) = r, for every vertex x in G, a graph G is said to be (D,r)-regular. In this paper, we conjecture that a graph admits a D-antimagic labeling if and only if it does not contain two vertices having the same D-neighborhood set. We also provide evidence that the conjecture is true. We present computational results that, for D = {1}, all graphs of order up to 8 concur with the conjecture. We prove that the set of (D,r)-regular D-antimagic graphs is closed under union. We provide examples of disjoint union of symmetric (D,r)-regular that are D-antimagic and examples of disjoint union of non-symmetric non-(D,r)-regular graphs that are D-antimagic. Furthermore, lastly, we show that it is possible to obtain a D-antimagic graph from a previously known distance antimagic graph