Representation Number for Complete Graphs Minus Stars

Abstract

Using the definition of the representation number of a graph modulo integers given by Erdős and Evans, we establish the representation number of a complete graph minus a set of disjoint stars. The representation number of a graph $G$ is the smallest positive integer $n$ for which there is a labeling of every vertex of $G$ with a distinct element of $\{0,1,2,\dots ,n-1\}$ such that two vertices are adjacent if and only if the difference of their labels is relatively prime to $n$. We apply known results to a complete graph minus a set of stars to establish a lower bound for the representation number; then show a systematic labeling of the vertices producing a representation that attains that lower bound. Thus showing that for complete graphs minus a set of disjoint stars, the established lower bound of the representation number modulo $n$ is indeed the representation number of the graph. Since the representation modulo an integer for a complete graph minus disjoint stars is attained using the fewest number of primes allowed by the lower bound, it follows that the corresponding Prague dimension will be determined by the largest star removed from the complete graph.