1
$\begingroup$

Let us consider a graph where edges can have weight 1 or -1, such a graph is called signed graph. In a signed graph, a cycle is called balanced cycle when product of weights on its edges is positive else it is called unbalanced cycle. If all possible cycles are balanced we call signed graph a balanced graph else it is called unbalanced graph.

Further, keeping the vertex set $V$ and edge set $E$ fixed, we can have $2^{|E|}$ possible signed graphs depending on 1 or -1 weight assigned to edges. Let $S$ be set of these possible signed graphs. In $S$ there will a set $B$ of balanced graphs and rest graphs will be in set $U$ of unbalanced graphs. Now it is proved that all the graphs in set $B$ have same spectrum i.e they have same set of eigenvalues.

(1) Is same thing can be said about graphs in set $U$?.

(2) I have observed that largest eigenvalue of a graph in set $B$ is greater than largest eigenvalue of graph in $U$. But I am not able to prove or disprove it.

$\endgroup$
1
  • $\begingroup$ If somebody can give me just a hint, it will be a great help $\endgroup$ Commented Jun 25, 2016 at 13:40

0

You must log in to answer this question.

Browse other questions tagged .