TY - JOUR

T1 - Graphs admitting antimagic labeling for arbitrary sets of positive numbers

AU - Matamala, Martín

AU - Zamora, José

N1 - Funding Information:
Partially supported by Basal program Grant PIA AFB-170001 and N?cleo Milenio Informaci?n y Coordinaci?n en Redes ICM/FIC RC130003.
Publisher Copyright:
© 2019 Elsevier B.V.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Hartsfield and Ringel in 1990 conjectured that any connected graph with q≥2 edges has an edge labeling f with labels in the set {1,…,q}, such that for every two distinct vertices u and v, fu≠fv, where fv=∑e∈E(v)f(e), and E(v) is the set of edges of the graph incident to vertex v. We say that a graph G=(V,E), with q edges, is universal antimagic, if for every set B of q positive numbers there is a bijection f:E→B such that fu≠fv, for any two distinct vertices u and v. It is weighted universal antimagic if for any vertex weight function w and every set B of q positive numbers there is a bijection f:E→B such that w(u)+fu≠w(v)+fv, for any two distinct vertices u and v. In this work we prove that paths, cycles, and graphs whose connected components are cycles or paths of odd lengths are universal antimagic. We also prove that a split graph and any graph containing a complete bipartite graph as a spanning subgraph is universal antimagic. Surprisingly, we are also able to prove that any graph containing a complete bipartite graph Kn,m with n,m≥3 as a spanning subgraph is weighted universal antimagic. From all the results we can derive effective methods to construct the labelings.

AB - Hartsfield and Ringel in 1990 conjectured that any connected graph with q≥2 edges has an edge labeling f with labels in the set {1,…,q}, such that for every two distinct vertices u and v, fu≠fv, where fv=∑e∈E(v)f(e), and E(v) is the set of edges of the graph incident to vertex v. We say that a graph G=(V,E), with q edges, is universal antimagic, if for every set B of q positive numbers there is a bijection f:E→B such that fu≠fv, for any two distinct vertices u and v. It is weighted universal antimagic if for any vertex weight function w and every set B of q positive numbers there is a bijection f:E→B such that w(u)+fu≠w(v)+fv, for any two distinct vertices u and v. In this work we prove that paths, cycles, and graphs whose connected components are cycles or paths of odd lengths are universal antimagic. We also prove that a split graph and any graph containing a complete bipartite graph as a spanning subgraph is universal antimagic. Surprisingly, we are also able to prove that any graph containing a complete bipartite graph Kn,m with n,m≥3 as a spanning subgraph is weighted universal antimagic. From all the results we can derive effective methods to construct the labelings.

KW - Antimagic graphs

KW - Complete bipartite graphs

KW - Split graphs

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

U2 - 10.1016/j.dam.2019.10.011

DO - 10.1016/j.dam.2019.10.011

M3 - Article

AN - SCOPUS:85074404116

SN - 0166-218X

VL - 281

SP - 246

EP - 251

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -