retagged by
9,800 views
35 votes
35 votes

Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as:

$$\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$$

Let $M$ be the adjacency matrix of $G$.

Define graph $G_2$ on the same set of vertices with adjacency matrix $N$, where 

$$N_{ij}=\left\{\begin{array} {lll} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.$$

Which one of the following statements is true?

  1. $\text{diam}(G_2)\leq\lceil \text{diam}(G)/2\rceil$
  2. $\lceil \text{diam}(G)/2\rceil<\text{diam}(G_2)< \text{diam}(G)$
  3. $\text{diam}(G_2) = \text{diam}(G)$
  4. $\text{diam}(G)< \text{diam}(G_2)\leq 2\;  \text{diam}(G)$
retagged by

6 Answers

0 votes
0 votes

Take example with n=4 vertices. Draw its graph and then its adjancy matrix M. Let it be G. Now take same 4 vertices for G2 and as per condition its adjancy matrix N =M^2 . After making matrix N, plot the graph. It will have self loops. Select and 2 vertices and find its diameter. It should satisfy option A

0 votes
0 votes
Consider any graph with n >= 3 (not complete graph ), you will get N as an adjacency matrix of the complete graph with self-loop on each vertex. Hence we can conclude that diam(G2) = 1, hence rest all the options will be neglected. Only option A, will stand out.
Answer:

Related questions

13 votes
13 votes
5 answers
1
Arjun asked Feb 18, 2021
8,019 views
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
6 votes
6 votes
1 answer
4
Arjun asked Feb 18, 2021
4,833 views
$$\begin{array}{|c|c|c|c|} \hline \textbf{Items} & \textbf{Cost} & \textbf{Profit %} & \textbf{Marked Price} \\ & \text{(₹)} & & \text{(₹)} \\\hline P &5,400 & -&5,86...