Representation of finite graphs as difference graphs of S-units, I

Abstract. Let S be a finite non-empty set of primes, ZS the ring of those rationals whose denominators are not divisible by primes outside S, and Z∗S the multiplicative group of invertible elements (S-units) in ZS. For a non-empty subset A of ZS, denote by GS(A) the graph with vertex set A and with an edge between a and b if and only if a − b ∈ Z∗S. This type of graphs has been studied by many people. In the present paper we deal with the representability of finite (simple) graphs G as GS(A). If A ′ = uA + a for some u ∈ Z∗S and a ∈ ZS, then A and A ′ are called S-equivalent, since GS(A) and GS(A′) are isomorphic. We say that a finite graph G is rep-resentable / infinitely representable with S if G is isomorphic to GS(A) for some A / for infinitely many non-S-equivalent A. We prove among other things that for any finite graph G there exist infinitely many finite sets S of primes such that G can be represented with S. We deal with the infinite representability of finite graphs, in particular cycles and complete bipartite graphs. Further, we consider the triangles in G for a deeper analysis. Fi-nally, we prove that G is representable with every S if and only if G is cubical. Besides combinatorial and numbertheoretical arguments, some deep Diophantine results concerning S-unit equations are used in our proofs. In Part II, we shall investigate these and similar problems over more general domains