1
$\begingroup$

This question is motivated from this post. Let $G$ be a given graph, for each vertex $v \in V$, I will label $v$ with $Triangle(v)$.

$Triangle(v) : $ means number of distinct triangles contain $v$.

Question : Is it a valid canonical form? Is computing this function easy (mean polynomial time)?

$\endgroup$
3
$\begingroup$

A canonical form of a graph is a mapping $C$ from the set of graphs to the set of graphs such that $C(G)$ is isomorphic to $G$, and $C(G) = C(H)$ iff $G$ is isomorphic to $H$. Your function doesn't map graphs to graphs, so it's not a canonical form.

A more relevant notion is a (complete) invariant. This is a mapping $I$ from the set of graphs to some other set such that $I(G) = I(H)$ iff $G$ is isomorphic to $H$. Your mapping, as stated, is not a graph invariant. For example, consider the graph consisting of a triangle plus an isolated vertex. Consider the graph $G$ in which the triangle vertices are $1,2,3$, and the graph $H$ in which the triangle vertices are $1,2,4$. The two graphs are isomorphic, but the vector $\mathit{Triangle}(\cdot)$ is different.

We can try to fix this problem by sorting the vector. This will ensure that the vectors corresponding to $G,H$ above are the same. However, consider $H'$, which consists of a triangle connected by an edge to a vertex. The graphs $H$ and $H'$ have the same sorted triangle vector, but are not isomorphic. So your suggestion is not even a complete invariant.

Finally, you ask how easy it is to calculate your function. There is a trivial $O(n^3)$ algorithm which goes over all triples of vertices, and this can be improved to $O(n^\omega)$ using fast matrix multiplication: if $A$ is the adjacency matrix of the graph, then $(A^3/2)_{vv}$ is the number of triangles containing $v$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.