Graph invariant is a property that holds for two isomorphic graphs. For example, degree sequence is graph invariant. We can write $d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ does not mean that $G \cong G'$.

I search for a name (and maybe some existing examples) for complementary graph invariant. Let $p$ be complementary graph invariant, then $p(G) = p(G') \Rightarrow G \cong G'$; however $p(G) \ne p(G')$ does not imply $G \ncong G'$. For example, for two isomorphic graphs adjacency matrix is such complementary graph invariant as two graphs with the same adjacency matrix are isomorphic, and there exists two isomorphic graphs with different adjacency matrices (take a permutation). So, is there a standard term/name for complementary graph invariants; and if so, where I can read more about them (examples, complexity, etc.)?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.