Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs
We consider a class of pattern graphs on q≥ 4 vertices that have q- 2 distinguished vertices with equal neighborhood in the remaining two vertices. Two pattern graphs in this class are siblings if they differ by some edges connecting the distinguished vertices. In particular, we show that if induced copies of siblings to a pattern graph in such a class are rare in the host graph then one can detec
