The coefficients of the characteristic polynomial of the adjacency matrix of an undirected graph on $n$ vertices reveal, for example, the number of edges, and the number of triangles in the graph.
The (global) clustering coefficient is the ratio of the number of triangles to the number of 3-paths (the connected graph on three vertices with two edges).
Is this coefficient apparent somehow as a function of the coefficients in the characteristic polynomial of the adjacency matrix, in a similar manner to the number of triangles?
My impression is that it is not, since (according to elementary linear algebra and algebraic graph theory) the determinants of the three $3 \times 3$ principal minors are all non-zero except the one referring to the 3-clique
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{pmatrix}
Hence the number triangles is present, but the number of 3-paths is not, since the 3-path minor
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0
\end{pmatrix}
has zero determinant. It may be related however to a function of powers of the adjacency matrix?
Answer
I have never heard about expressing the total number of connected triples in terms of characteristic polynomial coefficients. But your guess is correct, you can express both quantities in terms of certain sums of powers of the adjacency matrix $A$. The total number of triangles $t_G$ can be expressed as
$$
\textrm{tr}(A^3) = \sum_{i \in V} (A^3)_{ii},
$$
where
$$
(A^3)_{ii} = \sum_{j,k \in V:~j
is the number of triangles having $i$ as one of their vertices. Finally,
$$
t_G = \left( \sum_{i \in V} t_i \right) / 3 = \displaystyle\frac{{\textrm tr}(A^3)}{3}.
$$
No comments:
Post a Comment