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.

Let $G$ be any simple and undirected graph. Let $A$ be the adjacency matrix of $G$.

1) Let $B$ be the number $\tfrac16\mathrm{tr}(A^3)$. What does $B$ count? That is $B$ counts the number of....?

2) Suppose that $M$ is adjacency matrix of a tree. Explain why every element of the diagonal of $M^3$ must be zero.

3) Must every element of the diagonal of $M^2$ be zero?

share|improve this question
    
Just a short comment on 3, it is easy to prove that, in a simple graph, the diagonal entries of $M^2$ are exactly the degrees of the vertices. To understand why, think: how can you get from vertex $v$ to the same vertex in exactly 2 steps? –  N. S. Apr 24 '13 at 14:54

2 Answers 2

Let me extend the answer of Jp McCarthy. If $A$ is the adjacency matrix of $G$ then $X=A^k$ denotes the paths in $G$ in such a way that if $x_{i,j}=\ell$ then there are $\ell$ paths of length $k$ connecting vertex $i$ and $j$. Notice that the paths doesn't have to be simple, i.e., vertices and edges can be reused.

Regarding you questions:

  1. A diagonal entry encodes the cycles of length 3. For length 3, no path can reuse an edge or vertex. You count every 3-cycle 6 times (3 starting vertices and two orientations).
  2. A tree has no cycles, so no 3-cycles, therefore every entry on the diagonal of $M^3$ is zero.
  3. Every vertex not isolated is incident to at least one 2-cycle (go back and forth along one edge). So the answer is no. Indeed, if the tree is a spanning tree, none of the entries will be zero.
share|improve this answer
    
I am an immigrant. sometimes, when the time out, my professor speaks too fast, I don't completely understand what he is talking about. I can read it carefully and slowly to get the stuff from your explanation. Thank you very much. –  user73195 Apr 18 '13 at 16:41

I think...

  1. Number of three cycles

  2. No cycles

  3. No

You give more info and so will I :-)

share|improve this answer
    
Thanks for reply. That is my test. It is returned back without any comment or explanation. how can I upload the original paper? I scanned but don't know how to upload. –  user73195 Apr 18 '13 at 12:27
    
That was your test? Or is this a sample test? What do you not understand? –  Jp McCarthy Apr 18 '13 at 12:31
    
It'd be great if you could add more to the question, but I don't think adding a scanned copy of your returned test is the way to go about it. Perhaps you could just type in your thoughts on the questions? (New users cannot add images; this restriction is removed at 10 reputation.) –  Douglas S. Stones Apr 18 '13 at 12:37

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.