×

# Please help!

I came across this question in Graph Theory :

A graph on the vertex set $${1,2,3,n }$$ is often denoted by a matrix $$A$$ of size $$n$$ ,where $$aij$$ and $$aji$$ are equal to the number of edges with ends $$i$$ and $$j$$.

What is the $$Combinatorial$$ $$Interpretation$$ of the entries of $$A2$$ ?

Ps: This is posted on behalf of Azhaghu Roopesh M.

Note by Ishan Dasgupta Samarendra
2 years, 5 months ago

## Comments

Sort by:

Top Newest

The $$(i,j)$$th entry of $$A^2$$ denotes the number of paths of length $$2$$ between the vertices $$i$$ and $$j$$. The proof is easy. Let $$B=A^2$$. Then $B_{ij}=\sum_{k=1}^{n}A_{ik}A_{kj}$ Now let us interpret each of the terms in the above summation. $$A_{ik}$$ denote the number of paths of length $$1$$ from vertex $$i$$ to vertex $$k$$. Hence the product $$A_{ik}A_{kj}$$ denote the number of paths of length $$2$$ from $$i$$ to $$j$$, passing through $$k$$. Thus summing over all intermediate vertices $$k$$, we obtain the result. By induction, it also follows that $$(i,j)$$ th entry of the matrix $$A^{m}$$ denote the number of paths of length $$m$$ between the vertices $$i$$ and $$j$$. · 2 years, 5 months ago

Log in to reply

Thanks a lot sir ! I have a long way to go to match up with your skills :D

Btw I am reading Graph Theory from "A course in Combinatorics" , should I continue from there or perhaps you have a better suggestion for me ?

Thanks again . · 2 years, 5 months ago

Log in to reply

I followed Diestel's book on graph theory for basics. · 2 years, 5 months ago

Log in to reply

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...