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 original | Inglés |
---|---|
Páginas (desde-hasta) | 127-132 |
Número de páginas | 6 |
Publicación | Electronic Notes in Discrete Mathematics |
Volumen | 50 |
DOI | |
Estado | Publicada - 1 dic. 2015 |
Áreas temáticas de ASJC Scopus
- Matemáticas discretas y combinatorias
- Matemáticas aplicadas