Theorem 1.7
The characterristic polynomial of A ( G ) A(G) A ( G ) :
p ( A ( G ) , μ ) = d e t ( μ I n − A ( G ) ) = μ n + c 1 μ n − 1 + c 2 μ n − 2 + c 3 μ n − 3 + ⋯ + c n \begin{equation} p(A(G),\mu) = det(\mu I_{n} - A(G)) = \mu^{n} + c_1 \mu^{n-1} + c_2\mu^{n-2} + c_3\mu^{n-3} + \cdots + c_n \end{equation} p ( A ( G ) , μ ) = d e t ( μ I n − A ( G )) = μ n + c 1 μ n − 1 + c 2 μ n − 2 + c 3 μ n − 3 + ⋯ + c n
c 1 c_1 c 1 = 0;− c 2 -c_2 − c 2 is the number of edges of G G G ;− c 3 -c_3 − c 3 is twice the number of triangles in G G G ;c n = ( − 1 ) n det ( A ( G ) ) c_n = (-1)^{n}\det(A(G)) c n = ( − 1 ) n det ( A ( G )) , 这一条性质只能用在 c n c_n c n 为多项式的最后一项的时候,对于 c 4 ∼ c n − 1 c_4 \thicksim c_{n-1} c 4 ∼ c n − 1 请使用 Theorem 1.18Assume there is a Graph G G G with n n n vertices and its adjacency matrix is:
A ( G ) = ( a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ) A(G) = \begin{pmatrix} a_{11} &a_{12} &\cdots &a_{1n}\\ a_{21} &a_{22} &\cdots &a_{2n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n1} &a_{n2} &\cdots &a_{nn}\\ \end{pmatrix} A ( G ) = a 11 a 21 ⋮ a n 1 a 12 a 22 ⋮ a n 2 ⋯ ⋯ ⋱ ⋯ a 1 n a 2 n ⋮ a nn
For each i ∈ { 1 , 2 , . . . , n } i\in\{1,2, ..., n\} i ∈ { 1 , 2 , ... , n } , the number ( − 1 ) i c i (-1)^{i}c_i ( − 1 ) i c i is the sum of those principle minors of A ( G ) A(G) A ( G ) which have i i i rows and same i i i columns. (这个说法感觉和Theorem 1.18好像啊)
Since the principal submatrices are the adjacency matrices of induced subgraphs, then we get
c i = ( − 1 ) i ∑ ∣ U ∣ = i det A ( G [ U ] ) \begin{equation} c_i = (-1)^{i}\sum_{|U|=i}\det{A(G[U])} \end{equation} c i = ( − 1 ) i ∣ U ∣ = i ∑ det A ( G [ U ])
For − c 1 -c_1 − c 1 is the sum of eigenvalues, that is, also the trace of A ( G ) A(G) A ( G ) , andtr ( A ( G ) ) = ( a 11 + a 22 + ⋯ + a n n ) = 0 \text{tr}(A(G)) = (a_{11} + a_{22} + \cdots + a_{nn}) = 0 tr ( A ( G )) = ( a 11 + a 22 + ⋯ + a nn ) = 0
Then, c 1 = 0 c_1 = 0 c 1 = 0 .