Some necessary and sufficient conditions for diophantine graphs

Abstract

A graph G of order n is called Diophantine if there exists a labeling function f of vertices such that gcd(f(u),f(v)) divides n for every pair adjacent vertices u,v in G. This paper defines, studies and generalizes maximal Diophantine graphs D_n, determining their independence number, number of full-degree vertices, and clique number. These parameters establish necessary conditions for the existence of Diophantine labelings.