On Graphs Determined by Their $k$-Subgraphs

Abstract

The following problem is formulated:

Let $P(G)$ be a graph parameter and let $k$ and $\delta$ be integers such that $k>\ell \ge 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(⟨A⟩)=P(⟨B⟩)$. Characterize $G$.

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