Register

How to approach for calculating the number of paths of length n between 2 different vertices for a complete graph K4?

1,119 views
0 0 votes
If I have any complete graph given then what is the approach to be followed up for calculating the number of paths of length n because for large value of n ,computation would be tricky ,so how to proceed with such questions.

1 Answer

1 1 vote

M = Adjacency Matrix

MN = M x M x M ...n times.

MN [i][j] = P   means there are P paths of length N from vertex i to vertex j.

Voting & Accepting an answer helps improve the community
← Previous · GATE CSE 2015 | Set ...Next → · GATE CSE 2015 | Set ...
← Previous in category · any relation between...Next in category → · graphs - bipartite
Position:
Show:

Related questions

0 0 votes
1 1 answer
634
634 views
ronakagarawal asked Aug 23, 2023
634 views
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
0 0 votes
2 answers 2 answers
1.3k
1.3k views
yuuchan asked Jul 22, 2023
1,279 views
Ace workbook: If G is a complete bipartite graph with n vertices (n >= 2) and minimum number of edges, then matching number of G is ____
If G is a complete bipartite graph with n vertices (n >= 2) and minimum number of edges, then matching number of G is ____1n-1⌊n/2⌋⌈n/2⌉
1 1 vote
0 0 answers
3.0k
3.0k views
Ayush Upadhyaya asked Jun 6, 2018
2,961 views
Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices.
This is in reference to the below questionhttps://gateoverflow.in/473/gate2012-38My doubt here isIn this question, we can also solve like first we select 4 vertices out o...
0 0 votes
1 1 answer
3.9k
3.9k views
gshivam63 asked May 19, 2016
3,876 views
Upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices?