Estimating global subgraph counts by sampling (Q6162129)

This paper studies estimation of global subgraph counts through sampling. Given two graphs \(H\) and \(G\), let \(\mathrm{Hom}(H,G)\) be the set of homomorphisms. If \(H\) is a rooted graph with root \(o\) and \(\Delta\ge0\), let \(\mathrm{hom}_{\Delta}(H,G)\) be the number of homomorphisms, say \(\varphi\), from \(H\) to \(G\) such that the degree of the vertex \(\varphi(o)\ge\Delta\). It is shown that for any connected rooted graph \(H\) on \(h\ge1\) vertices, any graph \(G\) and \(\Delta\ge0\), it holds that \(\mathrm{hom}_{\Delta}(H,G)\le\sum_{v\in G}d_v^{h-1}1_{d_v\ge\Delta}\), where \(d_v\) the degree of \(v\).