Equality of graphs up to complementation

2020 
We prove the following: Let G and $$G'$$ be two graphs on the same set V of v vertices, and let k be an integer, $$4\le k\le v-4$$ . If for all k-element subsets K of V, the induced subgraphs $$G_{\restriction K}$$ and $$G'_{\restriction K}$$ have the same numbers of 3-homogeneous subsets, the same numbers of $$P_4$$ ’s, and the same numbers of claws or co-claws, then $$G'$$ is equal to G or to the complement $$\overline{G}$$ of G. We give also a similar result whenever the same numbers are modulo a prime.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    12
    References
    0
    Citations
    NaN
    KQI
    []