On Graphs Determined by Their \(k\)-Subgraphs

The following problem is formulated:

Let \(P(G)\) be a graph parameter and let \(k\) and \(\delta\) be integers such that \(k > \ell \geq 0\). Suppose \(|G| = n\) and for any two \(k\)-subsets \(A, B \subset V(G)\) such that \(|A \cap B| = \ell\) it follows that \(P(\langle A\rangle) = P(\langle B\rangle )\). Characterize \(G\).

We solve this problem for two parameters, the domination number and the number of edges modulo \(m\) (for any \(m \geq \ell\)). These solutions extend and are based on an earlier work that dated back to a 1960 theorem of Kelly and Merriell.