Directed graphs from exact covering systems

Dana Neidinger

Published 2020-10-05Version 1

Given an exact covering system $S = \{a_i \mod d_i : 1 \leq i \leq r\}$, we introduce the corresponding exact covering system digraph (ECSD \footnote{ECSD: Exact Covering System Digraph}) $G_S = G(d_1n+a_1, \ldots, d_rn+a_r)$. The vertices of $G_S$ are the integers and the edges are $(n, d_in+a_i)$ for each $n \in \mathbb{Z}$ and for each congruence in the covering system. We study the structure of these directed graphs, which have finitely many components, one cycle per component, as well as indegree 1 and outdegree $r$ at each vertex. We also explore the link between ECSDs that have a single component and non-standard digital representations of integers.