Additive edge labelings

Abstract

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.