## 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 K_{m,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∉{K_{1,m}, K_{2,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=K_{1,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