Abstract:

A graph has a representation modulo n if there exists an injective map f: {V(G)} > {0, 1, ... , n @ 1} such that vertices u and v are adjacent if and only if f(u)@f(v) is
relatively prime to n. The representation number is the smallest n such that G has a
representation modulo n. We seek the maximum value for the representation number
over graphs of a fixed order. Erdos and Evans provided an upper bound in their proof
that every finite graph can be represented modulo some positive integer. In this note
we improve this bound and show that the new bound is best possible (Refer to PDF file for exact formulas). 