Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that $$ ||z_1||=\ldots = ||z_n||=1. $$ If we know that there exist $a_1,\ldots, a_n \in {\mathbb R} - \{0 \}$ such that for all $i\in {\mathcal V}$, we have $$ z_i + \sum_{j=1}^{d_i}z_{i_j} = a_i z_i, %\forall i \in {\mathcal V} $$ where $i_1,\ldots, i_{d_i}$ are adjacent vertices of $i$, under what condition on structure of ${\mathcal G}$, can we deduce that for some $z\in {\mathbb C}$ and all $i \in {\mathcal V}$, we have $z_i \in \{z,-z\}$?

For example, If ${\mathcal G} = K_n$, the complete graph, then $$ z = z_1+\ldots+z_n = a_i z_i , \quad i=1,\ldots,N, $$ and since $a_i \in {\mathbb R} - \{0 \}$, we have $z_i = {z}/{a_i}$. Also, as $||z_1|| = \ldots = ||z_n||=1$, we have $a_i \in \{||z||,-||z||\}$, which proves the claim.

One can give an algebraic graph theoretic formulation of this problem as follows: Let ${\mathcal D}\subset {\mathbb R}^{n \times n}$ be the set of all non-singular diagonal real matrices and $A$ be the adjacency matrix of graph ${\mathcal G}$. If for some $D \in {\mathcal D}$, and $z_1, \ldots, z_n \in {\mathbb C}$ where $||z_1||=\ldots = ||z_n||=1$, we have $$ (A+I-D){\rm z} = 0 $$ where ${\rm z} = (z_1,\ldots,z_n)^T$, under what condition on $A$, can we deduce that ${\rm z} =c{\rm f}$, for some $c\in {\mathbb C}$ and ${\rm f} \in \{-1,1\}^n$?

Beside $K_n$, is there any other graph with this property?

  • $\begingroup$ Also I have proved this fact for trees by strong induction. $\endgroup$ Sep 16 '13 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.