Linear diophantine graphs

Abstract

This manuscript introduces linear Diophantine labelling, a new method for assigning labels to the vertices of finite, simple, undirected graphs. A key feature of this method is a divisibility condition imposed on the edges, incorporating number-theoretic properties into graph labelling. The study focuses on identifying maximal graphs that admit such labellings and computes their number of edges and the degree of each vertex. Number-theoretic techniques are employed to examine structural properties, including the characterization of maximum degree vertices and conditions for nonadjacent vertices. The manuscript also establishes necessary and sufficient conditions for vertices with equal degrees, offering new insights into the interaction between graph theory and number theory.