Adjacency matrix

mrgrieco · **Joined:** Sat, 26 Mar 2011 16:45:36 UTC **Posts:** 21

There is a connected graph on 15 vertices. Let be A the matrix that we get from its adjacency matrix by writing ones to its main diagonal (the rest of the elements remain unchanged). Prove that all of the elements of $A^{20}$ are positive integers.

Thank you very much for your help in advance!

outermeasure · **Posted:** Sun, 10 Apr 2011 12:14:15 UTC

mrgrieco wrote:

There is a connected graph on 15 vertices. Let be A the matrix that we get from its adjacency matrix by writing ones to its main diagonal (the rest of the elements remain unchanged). Prove that all of the elements of $A^{20}$ are positive integers.

Thank you very much for your help in advance!

Silly problem. Find a path and stays there.

More interesting would be to impose $\delta\geq 2$ and not add the loops.

mrgrieco · **Joined:** Sat, 26 Mar 2011 16:45:36 UTC **Posts:** 21

outermeasure wrote:

Silly problem. Find a path and stays there.

More interesting would be to impose $\delta\geq 2$ and not add the loops.

Thank you for your help.
To tell the truth, I didn't really catch the point. Could you please explain it?
Thank you!

Matt · **Joined:** Wed, 1 Oct 2003 04:45:43 UTC **Posts:** 9642

Each entry (i,j) of A^20 is nonzero iff there is a path of length 20 between node i and node j. Because the graph is connected, there is always a path between any two nodes. Because of the 1s on the diagonal, each node has a self-adjoining edge, and therefore it is trivially possible to increase the length of any non-cyclic path to 20.

S.O.S. Mathematics CyberBoard

Adjacency matrix

Who is online