Let G=(V,E) be an undirected, unweighted, connected graph. Its diameter is the…
GATE · 2021 · CS · Set 1 · Computer Science & IT
Let G=(V,E) be an undirected, unweighted, connected graph. Its diameter is the maximum, over all vertex pairs, of the length of a shortest path between them.
Let M be the adjacency matrix of G and let P=M2. Define a simple graph G2 on the same vertex set with adjacency matrix N by setting Nii=0 and, for i≠j, Nij=1 if Mij>0 or Pij>0; otherwise Nij=0.
Which one of the following statements is true?
- A.
diam(G2) ≤ ⌈diam(G)/2⌉
- B.
⌈diam(G)/2⌉ < diam(G2) < diam(G)
- C.
diam(G2) = diam(G)
- D.
diam(G) < diam(G2) ≤ 2 diam(G)
Attempted by 166 students.
Sign up free to check your answer
Sign up freeLoading lesson…