Arithmetic Progression Graphs
Michael J. Dinneen, Nan Rosemary Ke, Masoud Khosravani · Universal Journal of Applied Mathematics · 2014
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. We give conditions for paths, cycles, and bipartite graphs to have such a labeling. We then address the opposite problem of finding an edge labeled graph for a given finite arithmetic progression. We use a constructive procedure to fully characterize those finite arithmetic progressions that have representations as edge labeled graphs. Then by presenting a pseudo polynomial-time algorithm, we address a more general problem of finding edge labels for a graph when the vertex labels are given. Finally, we count the connected graphs, up to eight vertices, that accept such a labeling by using a simple algorithm that detects a valid edge labeling.