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

Improve this question
$\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$
    – Gordon Royle
    Commented 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$
    – Noam D. Elkies
    Commented Mar 22, 2015 at 3:00
  • $\begingroup$ Yes, $A$ is the adjacency matrix, and we need to add connected to the hypothesis. $\endgroup$
    – Gordon Royle
    Commented 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
    Commented 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$
    – Gordon Royle
    Commented Mar 23, 2015 at 1:24

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .