Representation Numbers and Prague Dimensions for Complete Graphs Minus a Disjoint Union of Paths

Anurag Agarwal1, Manuel Lopez1, Darren A. Narayan1
1School of Mathematical Sciences, RIT, Rochester, NY 14623-5604

Abstract

A graph is representable modulo \( n \) if its vertices can be assigned distinct labels from \(\{0,1,2,\ldots,n-1\}\) such that the difference of the labels of two vertices is relatively prime to \( n \) if and only if the vertices are adjacent. The representation number \( \text{rep}(G) \) is the smallest \( n \) such that \( G \) has a representation modulo \( n \). In this paper, we determine the representation number and the Prague dimension (also known as the product dimension) of a complete graph minus a disjoint union of paths.