Additive edge labelings
Let G=(V,E) G = ( V , E ) be a graph and d d a positive integer. We study the following problem: for which labelings fE:E?Zd f E : E ? Z d is there a labeling fV:V?Zd f V : V ? Z d such that f E ( i , j ) = f V ( i ) + f V ( j ) ( mod d ) , 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.
toric ideal graph labeling cycles incidence matrix kernel