Weighted antimagic labeling

Martín Matamala, José Zamora

Resultado de la investigación: Article

2 Citas (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 the following sums are all distinct: for each vertex u, ∑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 (w0,0)-antimagic labeling, for w0(u)=0, for each u∈V. In this work, we prove that all the complete bipartite graphs Kp,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≠K1,q, K2,2, then any connected graph G containing H as a spanning subgraph is antimagic.

Idioma originalEnglish
Páginas (desde-hasta)194-201
Número de páginas8
PublicaciónDiscrete Applied Mathematics
Volumen245
DOI
EstadoPublished - 20 ago 2018

Huella dactilar

Labeling
Connected graph
Graph in graph theory
Spanning Subgraph
Complete Bipartite Graph
Injective
Polynomial time
Polynomials
Distinct
Imply
Vertex of a graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Citar esto

Matamala, Martín ; Zamora, José. / Weighted antimagic labeling. En: Discrete Applied Mathematics. 2018 ; Vol. 245. pp. 194-201.
@article{1f6e39ad97b4449389947a7174a22e33,
title = "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,…,|E|+k} such that the following sums are all distinct: for each vertex u, ∑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 (w0,0)-antimagic labeling, for w0(u)=0, for each u∈V. In this work, we prove that all the complete bipartite graphs Kp,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≠K1,q, K2,2, then any connected graph G containing H as a spanning subgraph is antimagic.",
keywords = "Antimagic labeling, Complete bipartite graph, Graph labeling, Weighted antimagic labeling",
author = "Mart{\'i}n Matamala and Jos{\'e} Zamora",
year = "2018",
month = "8",
day = "20",
doi = "10.1016/j.dam.2017.05.006",
language = "English",
volume = "245",
pages = "194--201",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

Weighted antimagic labeling. / Matamala, Martín; Zamora, José.

En: Discrete Applied Mathematics, Vol. 245, 20.08.2018, p. 194-201.

Resultado de la investigación: Article

TY - JOUR

T1 - Weighted antimagic labeling

AU - Matamala, Martín

AU - Zamora, José

PY - 2018/8/20

Y1 - 2018/8/20

N2 - 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 the following sums are all distinct: for each vertex u, ∑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 (w0,0)-antimagic labeling, for w0(u)=0, for each u∈V. In this work, we prove that all the complete bipartite graphs Kp,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≠K1,q, K2,2, then any connected graph G containing H as a spanning subgraph is antimagic.

AB - 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 the following sums are all distinct: for each vertex u, ∑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 (w0,0)-antimagic labeling, for w0(u)=0, for each u∈V. In this work, we prove that all the complete bipartite graphs Kp,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≠K1,q, K2,2, then any connected graph G containing H as a spanning subgraph is antimagic.

KW - Antimagic labeling

KW - Complete bipartite graph

KW - Graph labeling

KW - Weighted antimagic labeling

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

U2 - 10.1016/j.dam.2017.05.006

DO - 10.1016/j.dam.2017.05.006

M3 - Article

AN - SCOPUS:85020419525

VL - 245

SP - 194

EP - 201

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -