• Find a connected graph of n vertices for which each of the powers AG^1 , AG^2 , . . . of the adjacency matrix contains some zero elements.

for this I drew two vertices and linked them together with one edge, then I built the adjacency matrix with rows (0 1) and (1 0). I showed that for n>1, AG^n is the identity matrix thus containing some zero elements. I just have not proved this for n vertices, I'm just at two. Can I take a step further and say that any n vertices connected in a straight line satisfy the conditions ?

  • $\begingroup$ The path with one edge can also be thought of as the complete graph $K_2$, the complete bipartite graph $K_{1,1}$, or the unique tree on two vertices. So these four families, as well as any others you can think of, are natural ways to try to extend your observations to $n$ vertices. (Also, your calculation as stated is not correct: for the path with one edge, $AG^k=I$ only for even $k$. But that's good enough to get what you want: what happens for odd $k$?) $\endgroup$ – Eric Stucky Nov 3 '16 at 0:32

I think you example works for all $n>1$(though your calculation is indeed not correct as pointed in the first comment). To prove it, enumerate the vertices with $1,2,\ldots ,n$. The entry $(u,v)$ of the matrix $AG^i$ contains the number of paths of length i between u and v in the graph G. Then for each i, either the entry (1,1) or (1,2) is 0, since all the paths starting at 1 and going back to 1 are of even length and all such paths from 1 to 2 are of odd length.

Another good example will be the graph having one vertex connected to all the other $n-1$ vertices with one edge each(and no other edges in the graph). You can try to do similar reasoning here for odd/even length of certain paths.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.