Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor


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
Página de inicio:444
Página de fin:452
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math


  • DasGupta, B., Enciso, G.A., Sontag, E., Zhang, Y., Algorithmic and complexity results for decompositions of biological networks into monotone subsystems (2006) Lecture Notes in Computer Science, 4007, pp. 253-264. , Experimental Algorithms, Springer, Berlin, Heidelberg
  • Gallian, J.A., (2009),, A dynamic survey of graph labeling January; Graham, R.L., Sloane, N.J.A., On additive bases and harmonious graphs (1980) SIAM Journal of Algebraic and Discrete Methods, 1 (4), pp. 382-404
  • Grossman, J.W., Kulkarni, D.M., Schochetman, I.E., On the minors of an incidence matrix and its Smith normal form (1995) Linear Algebra and its Applications, 218 (1-3), pp. 213-224
  • Harary, F., (1969) Graph Theory, , Addison-Wesley
  • Kannan, R., Bachem, A., Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix (1979) SIAM Journal on Computing, 8, pp. 499-507
  • Lee, S.-M., Schmeichel, E., Shee, S., On felicitous graphs (1991) Discrete Mathematics, 93, pp. 201-209
  • Sturmfels, B., (1995) University Lecture Series, 8. , American Mathematical Society
  • Villareal, R., Rees algebras of edge ideals (1995) Communications in Algebra, 23 (9), pp. 3513-3524


---------- APA ----------
Dickenstein, A. & Tobis, E.A. (2010) . Additive edge labelings. Discrete Applied Mathematics, 158(5), 444-452.
---------- CHICAGO ----------
Dickenstein, A., Tobis, E.A. "Additive edge labelings" . Discrete Applied Mathematics 158, no. 5 (2010) : 444-452.
---------- MLA ----------
Dickenstein, A., Tobis, E.A. "Additive edge labelings" . Discrete Applied Mathematics, vol. 158, no. 5, 2010, pp. 444-452.
---------- VANCOUVER ----------
Dickenstein, A., Tobis, E.A. Additive edge labelings. Discrete Appl Math. 2010;158(5):444-452.