GATE CS 2021 Set 1 Q.46 (CS Q.36): Graph Theory

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

\text{diam}(G) = \max_{u, v} \{\text{the length of shortest path between } u \text{ 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} = \begin{cases} 1 & \text{if } M_{ij} > 0 \text{ or } P_{ij} > 0, \text{ where } P = M^2 \\ 0 & \text{otherwise} \end{cases}

Which one of the following statements is true?

$\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$

$\lceil \text{diam}(G)/2 \rceil < \text{diam}(G_2) < \text{diam}(G)$

$\text{diam}(G_2) = \text{diam}(G)$

$\text{diam}(G) < \text{diam}(G_2) < 2\,\text{diam}(G)$

Official answer and solution

Official answer: A
From: Official GATE 2021 answer key

Solution

Relate the shortest path lengths in G2 to the shortest path lengths in G based on paths of length at most 2.

In the graph $G_2$ , an edge $(u, v)$ is present if $M_{uv} > 0$ (an edge exists between $u$ and $v$ in $G$ ) OR $P_{uv} = (M^2)_{uv} > 0$ (there is a path of length 2 between $u$ and $v$ in $G$ ).

Thus, a single edge in $G_2$ can traverse up to 2 edges of $G$ . If the shortest path distance between any two vertices $u$ and $v$ in $G$ is $d_G(u, v)$ , then in $G_2$ one can traverse that same path taking hops of size up to 2 edges. Consequently, the shortest path distance in $G_2$ satisfies:

d_{G_2}(u, v) \le \left\lceil \frac{d_G(u, v)}{2} \right\rceil

Taking the maximum over all pairs of vertices $(u, v)$ :

\text{diam}(G_2) = \max_{u, v} d_{G_2}(u, v) \le \max_{u, v} \left\lceil \frac{d_G(u, v)}{2} \right\rceil = \left\lceil \frac{\text{diam}(G)}{2} \right\rceil

Hence, $\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$ , which matches option A.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 46 of 65, printed as CS Q.36
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source