Abstract:
In this paper we study the problem of labeling the edges of a graph with positive
integers such that the sequence of the sums of incident edges of each vertex makes a
finite arithmetic progression. First, by presenting a pseudo polynomial-time algorithm,
we address a more general problem of finding edge labels for a graph with given vertex
labels. We then give necessary and sufficient conditions for paths and cycles to have
such labeling. We also give an algorithm that finds a valid edge labeling by solving a
system of linear equations. As the result, we list the graphs that do not accept such a
labeling for all connected graphs with up to eight vertices. Also the opposite problem of
finding an edge labeled graph for a given finite arithmetic progression is studied. We use a
constructive procedure to fully characterize those finite arithmetic progressions that have
representations as edge labeled graphs.