Additive edge labelings

Let G=(V,E)G=(V,E) be a graph and dd a positive integer. We study the following problem: for which labelings fE:E→ZdfE:E→Zd is there a labeling fV:V→ZdfV:V→Zd such that fE(i,j)=fV(i)+fV(j)(modd), for every edge (i,j)∈E(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.