Let G = (V, E) be a graph and d a positive integer. We study the following problem: for which labelings fE : E → Zd is there a labeling fV : V → Zd such that fE (i, j) = fV (i) + fV (j) (mod d), for every edge (i, j) ∈ E? We also explore the connections of the equivalent multiplicative version to toric ideals. We derive a polynomial algorithm to answer these questions and to obtain all possible solutions. © 2009 Elsevier B.V. All rights reserved.
Documento: | Artículo |
Título: | Additive edge labelings |
Autor: | Dickenstein, A.; Tobis, E.A. |
Filiación: | Departamento de Matemática, FCEN, Universidad de Buenos Aires, Argentina Departamentos de Matemática y Computación, FCEN, Universidad de Buenos Aires, Argentina |
Palabras clave: | Cycles; Graph labeling; Incidence matrix; Kernel; Toric ideal; Following problem; Graph labelings; Incidence matrices; Labelings; Multiplicative version; Polynomial algorithm; Positive integers; Possible solutions; Toric ideals; Labeling |
Año: | 2010 |
Volumen: | 158 |
Número: | 5 |
Página de inicio: | 444 |
Página de fin: | 452 |
DOI: | http://dx.doi.org/10.1016/j.dam.2009.10.006 |
Título revista: | Discrete Applied Mathematics |
Título revista abreviado: | Discrete Appl Math |
ISSN: | 0166218X |
CODEN: | DAMAD |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v158_n5_p444_Dickenstein.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v158_n5_p444_Dickenstein |