Weighted antimagic labeling: An algorithmic approach

Martín Matamala, José Zamora

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

1 Cita (Scopus)

Resumen

A graph G= (V, E) is weighted-k-antimagic if for each w:V→R, there is an injective function f: E→{1, ..., |E| + k} such that for each vertex u the following sums are all distinct: ∑v:uv∈Ef(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)-antimagic labeling where w(u)=0 for each u∈ V. In this work, an algorithm is proposed that computes in polynomial time a (w,0)-antimagic labeling of the complete bipartite graph Km,n=(V, E), when 2≤n≤m and m≥3, for any function w:V→R. On the one hand, the existence of this labeling provides new support to a well-known conjecture of Hartsfield and Ringel asserting that any connected graph with at least two edges is antimagic. More precisely, for each complete partite graph H, with H∉{K1,m, K2,2} we prove that any connected graph G containing H as an spanning subgraph is weighted-0-antimagic. Moreover, given a function w, a (w,0)-antimagic labeling can be computed in polynomial time. On the other hand, the ideas used in the design of our algorithm allows us to give a short algorithmic proof of the following fact: each connected graph G on n vertices having a universal vertex is weighted-1-antimagic, unless G=K1,n-1 and n is even.

Idioma originalInglés
Páginas (desde-hasta)127-132
Número de páginas6
PublicaciónElectronic Notes in Discrete Mathematics
Volumen50
DOI
EstadoPublicada - 1 dic 2015

Áreas temáticas de ASJC Scopus

  • Matemáticas discretas y combinatorias
  • Matemáticas aplicadas

Huella Profundice en los temas de investigación de 'Weighted antimagic labeling: An algorithmic approach'. En conjunto forman una huella única.

Citar esto