On $t$-edge-balanced graphs

Abstract

A graph $G$ on $n$ vertices with $k$ edges is $t$-edge-balanced if every graph on $n$ vertices with $t$ edges is contained in exactly the same number of subgraphs of $K_n$ isomorphic to $G$. Despite the existence of infinite families of $2$-edge-balanced graphs, no $t$-edge-balanced graphs were known for $t\ge 3$. This paper resolves the existence question for $t\ge 3$ in two directions. For $t=3$, we derive necessary arithmetic conditions on the parameters $(n,k)$ and use a simulated annealing search to find the first known examples of $3$-edge-balanced graphs. For $t\ge 4$, we prove that no nontrivial $t$-edge-balanced graphs exist.