Let $G$ be an undirected graph and the corresponding adjacency matrix be $A$. Let $v$ be a cut-vertex of $G$. Let $G_1, G_2,\dots, G_k$ are the connected components of the induced graph $G-v$ ( the subgraph resulting after the removal of $v$ and its incident edges from $G$). Let $\phi(G)$ denote the characteristic polynomial of $G$, that is, $\phi(G)=\det (A-\lambda I)$ . Then the following relation holds. $$\phi(G)=\phi(G_1)\phi(G-G_1)+\phi(G_1+v)\prod_{i=2}^k\phi(G_i)+\lambda \prod_{i=1}^k\phi(G_i).$$ Assume that the nullity (number of zero eigenvalues) of $G_1$, denoted by $\eta(G_1)$ satisfies $\eta(G_1)=\eta(G_1+v)+1.$ Then without using ranks of graphs prove the following: $$\eta(G)=\sum_{i=1}^k\eta(G_1)-1=\eta(G-v)-1.$$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is the motivation for not using the ranks of the graphs? $\endgroup$– Arnaud MortierCommented Jan 2, 2018 at 15:10
-
$\begingroup$ Actually, this relation also holds for directed graphs ( using weakly connected components ). But for the directed graph, using rank we cannot say about the number of zero eigenvalues. I was wondering if we somehow prove the above for undirected graph (without using rank), then using similar procedure we may say something about the number of zero eigenvalues for the directed case. $\endgroup$– Ranveer SinghCommented Jan 2, 2018 at 15:45
Add a comment
|