Weighted antimagic labeling

Abstract

A graph G = (V, E) is weighted-k-antimagic if for each w : V -> R, there is an injective function f : E -> {1,...,vertical bar E vertical bar + k} such that the following sums are all distinct: for each vertex u, Sigma(v:uv is an element of E)f (uv) + w(u). When such a function f exists, it is called a (w, k)-antimagic labeling of G. A connected graph G is antimagic if it has a (w(0), 0)-antimagic labeling, for w(0)(u) = 0, for each u is an element of V.

In this work, we prove that all the complete bipartite graphs K-p,K-q, are weighted-0-antimagic when 2 <= p <= q and q >= 3. Moreover, an algorithm is proposed that computes in polynomial time a (w, 0)-antimagic labeling of the graph. Our result implies that if H is a complete partite graph, with H not equal K-1,K-q, K-2,K-2, then any connected graph G containing H as a spanning subgraph is antimagic. (C) 2017 Elsevier B.V. All rights reserved.