2
$\begingroup$

if a graph with adjacency matrix $A$ and Laplacian $L$ has $k$ distinct eigenvalues then does this fact naturally help define or prove existence of a polynomial $p$ of degree $k-1$ such that $[p(A)]_{ij} \neq 0, \forall i,j$ ? (and similarly for $L$ with may be a different polynomial but with the same degree)


(prove the above without using the fact that diameter of a graph is bounded by $k$)

$\endgroup$
7
  • $\begingroup$ Use the fact that the $ij$-entry of $A^s$ is the number of walks of length $s$ from $i$ to $j$ and then everything follows almost immediately from that. $\endgroup$ Mar 22, 2015 at 2:39
  • $\begingroup$ Wait, a disconnected graph does not satisfy this condition for any polynomial $p$, and can easily have all eigenvalues distinct (e.g. the graph with 3 vertices and 1 edge). [Presumably $A$ is the adjacency matrix, though the problem statement never actually defines $A$.] $\endgroup$ Mar 22, 2015 at 3:00
  • $\begingroup$ Yes, $A$ is the adjacency matrix, and we need to add connected to the hypothesis. $\endgroup$ Mar 22, 2015 at 3:38
  • $\begingroup$ @GordonRoyle I feel you are using the theorem that the diameter of the graph is upper bounded by the number of distinct eigenvalues. Can you not use that? Like think of this proof as a step in trying to prove that! $\endgroup$
    – user6818
    Mar 22, 2015 at 18:56
  • $\begingroup$ @user6818 I can see no way of avoiding use of the diameter. The condition that p(A) has no zeros seems to rely on the existence of walks - Noam's example that the statement is false for disconnected graphs shows that it cannot be deduced entirely from the linear algebra. $\endgroup$ Mar 23, 2015 at 1:24

1 Answer 1

2
$\begingroup$

Please see Proposition 1.3.3 in Brouwer-Haemers book available here: http://homepages.cwi.nl/~aeb/math/ipm/

Let $\Gamma$ be a connected graph with diameter $d$. Then $\Gamma$ has at least $d+1$ distinct adjacency eigenvalues, at least $d+1$ distinct Laplace eigenvalues and at least $d+1$ signless Laplacian eigenvalues.

As they state in the proof, this result works for any matrix $M$ whose rows and columns are indexed by the vertices of $\Gamma$ and where $M_{x,y}>0$ if and only if $x$ is adjacent to $y$.

$\endgroup$

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.