Let us consider a graph $G$ having $m$ number of complete sub-graphs $K_{n_1},K_{n_2},...,K_{n_m}$ which have size $n_1,n_2,...,n_m$ respectively. Further $\forall i$, one vertex of $K_{n_i}$ is connected to one vertex of $K_{n_{i+1}}$ by an edge. Similarly, one vertex (different from previous one) of $K_{n_i}$ is connected to one vertex of $K_{n_{i-1}}$ by an edge. In this way, complete sub-graphs are connected in chain to form $G$. Find the eigenvalues of adjacency matrix of $G$.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Where did this come from? A path of length $d=2m-2$ fits this description with $n_1=n_m=1$ and otherwise $n_i=2.$ The $d$ eigenvalues are well known and nice, but not trivial. For your graph you would have $n$ eigenvalues. You can see that all but about $d$ are equal to $-1$ (add an identity matrix and consider the rank). The other $d$ or so are not as nice as for a path. $\endgroup$– Aaron MeyerowitzCommented Jun 8, 2016 at 20:09
-
$\begingroup$ I am working on signed graphs. There is concept in signed graphs that, if a signed graph can be clustered in groups of nodes such that each edge inside a group is positive while each edge between any two group is negative we call such signed graph a balanced graph. Eigenvalues of these graphs describes useful properties. Above problem also having groups(here complete sub-graphs) connected in chain by an edge to its adjacent groups. Although my interest is in when the connecting edge is negative, but I think I can solve it if you help me considering it as positive edge. $\endgroup$– Ranveer SinghCommented Jun 9, 2016 at 9:07
-
$\begingroup$ What do you mean by a positive or negative edge? An eigenvector of the usual adjacency matrix assigns values to the vertices. $\endgroup$– Aaron MeyerowitzCommented Jun 9, 2016 at 16:55
-
$\begingroup$ In social networks negative edge denotes hatred or enemity between two nodes. In adjacency matrix of signed graph/network we put (i,j)th entry equals to 1 if edge between nodes i & j is postive. Similary (i,j)th entry equals to -1 if edge between nodes i & j is negative otherwise (i,j)th entry is 0. $\endgroup$– Ranveer SinghCommented Jun 10, 2016 at 4:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The characteristic polynomial of a complete graph with $n$ vertices is $(x-n+1)(x+1)^{n-1}$. By deleting a vertex from the complete graph $K_n$, the remaining graph is the complete graph $K_{n-1}$ with characteristic polynomial $(x-n+2)(x+1)^{n-2}$.
Consider subgraph $G_i$ of the graph $G$ that is constructed from the union of two complete subgraphs $K_{n_i}$ and $K_{n_{i+1}}$ of $G$ and the edge which connect these two subgraphs. By using the following theorem of Schwenk, you can find the characteristic polynomial of $G_i$.
Schwenk A. J., Computing the characteristic polynomial of a graph, in Graphs
and Combinatorics (eds. Bari, R., Harary, F.), Springer-Verlag (New York), 1974.
For any edge $uv$ of the graph $G$,
\begin{align*} P_G(x)=P_{G-uv}(x)-P_{G-u-v}(x)-2\sum_{Z\in C(uv)}P_{G-V(Z)}(x), \end{align*} where $C(uv)$ denotes the set of all cycles containing $uv$.
Since the edge which connect the two complete subgraphs in $G_i$ is not contained in any cycles, the third part of the above formula is zero. So, the characteristic polynomial of $G_i$ is \begin{align*} (x-n_i+1)(x+1)^{n_i-1}(x-n_{i+1}+1)(x+1)^{n_{i+1}-1}\\ -(x-n_i+2)(x+1)^{n_i-2}(x-n_{i+1}+2)(x+1)^{n_{i+1}-2} \end{align*} Such as above and by using the above theorem repeatedly, you can find the characteristic polynomial of $G$. As Meyerowitz mentioned, you can find some roots of this characteristic polynomial that is equal to $-1$ simply, but finding some of them is difficult in general.
answered Jun 8, 2016 at 20:42
-
$\begingroup$ Thanks a lot. Please, give me some reference to above theorem of Schwenk, I want to read more about it. $\endgroup$ Commented Jun 10, 2016 at 5:56
-
$\begingroup$ @Ranveer Singh: I added a reference to the answer. $\endgroup$ Commented Jun 10, 2016 at 9:47