REPRESENTATIONS OF GRAPHS MODULE-N

A graph is representable module n if its vertices can be labeled with distinct integers between 0 and n, the difference of the labels of two vertices being relatively prime to n if and only if the vertices are adjacent. Erdos and Evans recently proved that every graph is represen table module some positive integer. We derive a combinatorial formulat ion of representability module n and use it to characterize those grap hs representable module certain types of integers, in particular integ ers with only two prime divisors. Other facets of representability are also explored. We obtain information about the values of n module whi ch paths and cycles are representable. (C) 1994 John Wiley & Sons, Inc .