Arithmetic Progression Graphs

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.