Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Could you help me with the following?

Find a connected graph for which each of the matrices $A^{k}_{G}, \ k \ge 0$ contains $0$s.

And another one:

Show that a graph is connected if and only if $(I+A_{G})^{n}$ doesn't contain $0$s for $n$s large enough.

I know that in a matrix $A^{k}_{G} \ \ a_{ij}^{k}$ is the number of walks length k from $v_{i}$ to $v_{j}$. And if we multiply matrices we are simply concatenating walks. But I don't know how (or if) we can use it proving the first one.

As to the second one I am completely at loss.

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

HINT: For the first question, consider the graph with two vertices and one edge. More generally, consider any bipartite graph. The point is that a walk with ends in different vertex sets has odd length, while a walk with ends in the same vertex set has even length.

One direction of the second question is easy. For the other direction, suppose that $G$ is connected. Then there is a positive integer $m$ such that for any two vertices $u$ and $v$ of $G$ there is a walk from $u$ to $v$ of length at most $m$. Show that $(I+A_G)^n$ has no zeroes if $n\ge m$. The key is to show that the $(i,j)$ entry in $(I+A_G)^n$ is the number of walks of length at most $n$ from $v_i$ to $v_j$. Try it first for $n=2$; try to see why the $1$’s on the main diagonal of $I+A_G$ correspond to standing in place on a vertex for one ‘step’ instead of actually moving to a different vertex.

share|improve this answer
    
So what you mean is that no matter how many times should we concatenate walks in a bipartite graph, there will always be some vertices which won't be connected, right? –  Hagrid Jan 13 '13 at 18:09
1  
@Hagrid: If $u$ and $v$ are in different vertex sets, there is no walk from $u$ to $v$ of length $0,2,4,6,\dots$, so you’ll get a $0$ in the corresponding entry of $A_G^{2n}$ for all $n\ge 0$. And if $u$ and $v$ are in the same vertex set, ... ? –  Brian M. Scott Jan 13 '13 at 18:11
    
Well, if $u$ and $v$ are in the same set of vertices of a bipartite graph, then the can't be connected, then from the way we multiply matrices we know that if $a_{ij}=0$, then $a_{ij}^{k}=0$ –  Hagrid Jan 13 '13 at 18:16
1  
@Hagrid: No, there may well be walks from $u$ to $v$; they just have to have even length. Thus, the appropriate entry in $A_G^{2n+1}$ will always be $0$. Since you’re having trouble with this, I strongly suggest that you look at the simplest example, the graph with two vertices and one edge. Its adjacency matrix is $A=\pmatrix{0&1\\1&0}$. What are the powers of $A$? You can easily compute them by hand. –  Brian M. Scott Jan 13 '13 at 18:19
1  
@Hagrid: You have the powers right, but I don’t think that you’re interpreting them correctly. There are just two vertices, say $v_1$ and $v_2$. You have $A^n=A=\pmatrix{0&1\\1&0}$ for all odd $n$; this means that if $n$ is odd, there is no walk of length $n$ from $v_1$ to $v_1$ or from $v_2$ to $v_2$, but there is one from $v_1$ to $v_2$. You have $A^n=I$ for all even $n$; this means that if $n$ is even, there is no walk of length $n$ from $v_1$ to $v_2$, but there is one from $v_1$ to $v_1$ and from $v_2$ to $v_2$. All of these facts should also be pretty clear when you look at $G$: $*-*$. –  Brian M. Scott Jan 13 '13 at 18:35
show 8 more comments

Hint: Each power $k$ gives you the number of paths of $k$ legnths between vertices $i,j$ for the matrix entry $a_{ij}$. You can think of graphs that restrict some kind of paths, for example bipartite graphs: two vertices of the same set can only have paths of even length, and two of different sets can only have paths of odd lengths...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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