943 views
0 votes
0 votes
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y

What would be maximum path length between any two vertices of graph ?

2 Answers

Best answer
5 votes
5 votes

For maximum path length , we need to consider the maximum chain length possible..

So if we start from 2 we get chains as :  2 -- 4 -- 8

                                                           2 -- 6 -- 12

                                                           2 -- 4 -- 12

     if we start from 3 we get chains as    :  3 -- 6 -- 12

                                                              3 -- 9

     if we start from 3 we get chains as    :    5 -- 10

     Vertices 7 and 11 remain disconnected..

Moreover the graph will be a directed one because x divides y is only one way

Assuming finite answer , hence the correct answer should be 2..[May be 3 -- 6 -- 12 etc ]

edited by

Related questions

1 votes
1 votes
1 answer
1
Tesla! asked Apr 30, 2017
534 views
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhich vertex will have highest in deg...
3 votes
3 votes
3 answers
2
Tesla! asked Apr 30, 2017
1,112 views
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yFind number of strongly connected com...
1 votes
1 votes
1 answer
3
Tesla! asked Apr 21, 2018
668 views
Consider Undirected Graph Ghaving vertex V {A,B,C,D,E}and edge pair as E {AB BD BE AC CE CD}A) Given graph is disconnectedB) Given graph is completeC) Given graph has ver...