Connected components of arithmetic graphs

Abstract

Let$R \subseteq \left\{ {1,2,...,m} \right\}$. LetG _m (R) be the graph whose vertices are the numbers 1, 2, ...,m and whose edges are all pairs {a, b} such thata+b≡r (modm) for somer∈R. LetC _m (R) be the number of connected components ofG _m (R). Letd be the greatest common divisor ofm and the differencesr _j −r _j or allr _i ,r _j ∈R. ThenC _m (R) is equal to (i) (d+1)/2 ifd is odd, (ii)d/2 ifd is even andr is odd for allr∈R, or (iii) (d/2)+1 ifd is even andr is even for allr∈R.