1
$\begingroup$

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$.

$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Jun 10, 2016 at 4:56

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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