From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs

Simon Döring, Dániel Marx, Philip Wellnitz

A graph property is a function $\Phi$ that maps every graph to {0, 1} and is invariant under isomorphism. In the $\#IndSub(\Phi )$ problem, given a graph $G$ and an integer $k$, the task…