zbMATH — the first resource for mathematics

An upper bound for the representation number of graphs with fixed order. (English) Zbl 1023.05104
Summary: A graph has a representation modulo \(n\) if there exists an injective map \(f\: V(G)\rightarrow \{0,1,\dots ,n-1\}\) such that vertices \(u\) and \(v\) are adjacent if and only if \(\left|f(u)-f(v)\right|\) 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. P. Erdős and A. B. Evans [J. Graph Theory 13, 593-595 (1989; Zbl 0691.05053)] 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.

05C62 Graph representations (geometric and intersection representations, etc.)
Full Text: EuDML