Additive edge labelings

作者：Dickenstein Alicia; Tobis Enrique A^*

来源：Discrete Applied Mathematics, 2010, 158(5): 444-452.

DOI：10.1016/j.dam.2009.10.006

• Graph labeling
• Cycles
• Incidence matrix
• Toric ideal
• Kernel

Let G = (V, E) be a graph and d a positive integer. We study the following problem: for which labelings f(E) : E -> Z(d) is there a labeling f(V) : V -> Z(d) such that f(E)(i, j) = f(V)(i) + f(V)(j) (mod d), for every edge (i, j) is an element of 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.

• 出版日期2010-3-6