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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.