retagged by
9,796 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

37 votes
37 votes

A walk consists of an alternating sequence of vertices and edges consecutive elements of which are incident, that begins and ends with a vertex. 

In simple words, Walk from vertex $w$ to $v$ is sequence of “adjacent edges”, starting from $w,$ ending at $v,$ possibly with repetition of vertices or edges or both. Length of a walk is the number of edges on it.

The Adjacency Matrix of a Graph :

The adjacency matrix $M$ of a undirected graph is defined by numbering the vertices, say from $1$ up to $n$, and then putting $M_{ij} = M_{ji} = 1 $ if there is an edge from $i$ to $j$, and $M_{ij} = 0$ otherwise.

We can do the same for a digraph: putting $M_{ij} = 1$ if there is an edge from $i$ to $j$, and $M_{ij} = 0$ otherwise.

Refer here to understand Adjacency Matrix of a Graph :

https://en.wikipedia.org/wiki/Adjacency_matrix

http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section1-1.pdf

Powers of the Adjacency Matrix :

Let $G$ be a graph, $n \in \mathbb{N}$, Let $M$ be the adjacency matrix of $G.$

The powers of the adjacency matrix counts things. In particular,

Entry $i, j$ in $M^n$ gives the number of walks from $i$ to $j$ of length $n.$

The proof is by induction argument. For example, the number of walks of length 2 is the number of vertices $k$ such that there is an edge from $i$ to $k$ and an edge from $k$ to $j$. And this is exactly the $i, j$ entry in $M^2$ , by the definition of matrix multiplication.

Also, NOTE that for any graph $G$ (directed or undirected), we can see that, every entry in adjacency matrix basically tells us that Number of walks of length $1$ between the corresponding vertices of that entry, So, if $M_{ij} $ is 1, it means there is walk of length $1$ from $i$ to $j,$ which is basically edge from $i$ to $j.$


Coming to the given question, for undirected connected graph $G,$ $M$ is its adjacency matrix. So, every non-zero entry $M_{ij}$ in $M$ tells us that there is a walk of length $1$ between vertices $i$ and $j$ in $G$.

Given $P = M^2,$ So,  every non-zero entry $P_{ij}$ in $P$ tells us that there is a walk of length $2$ between vertices $i$ and $j$ in $G$.  

( In particular, every entry $P_{ij}$ in $P$ tells us the number of walks of length $2$ between vertices $i$ and $j$ in $G$. )

By the definition of matrix $N$, $N_{ij} $ is $1$ iff either $M_{ij}$ is $1$ Or $P_{ij}$ is $1,$ So, we can say that $N_{ij} $ is $1$ iff there is a walk of length 1 or 2 or both between vertices $i,j$ in $G.$

$N$ is adjacency matrix of graph $G_2, $ So, in Graph $G_2,$ we have edge between $i,j$ iff there is walk of length 1 or 2 between $i,j$ in $G.$ 

So, conclusive point is that :

To get $G_2$ from $G,$ we need to keep the $G$ as it is, but also we need to add edge between vertex $w,u$ if there is walk of length 2 between $w,u.$ For undirected connected graph of at least two vertices, it will also bring self loops for every vertex.  

So, diameter of $G_2$ will definitely become almost half of diameter of $G.$ 

If Diameter of $G$ is odd number, say $d =7,$ then Diameter of $G_2$ will become  $\lceil d/2 \rceil = 4.$ 

If Diameter of $G$ is even number, say $d =6,$ then Diameter of $G_2$ will become $\lceil d/2 \rceil = 3.$ 

Option A is correct. But I think (Point me out if I am wrong) that $Diam(G_2) = \lceil Diam(G)/2 \rceil.$

http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section1-1.pdf

https://www.cusb.ac.in/images/cusb-files/2020/el/math/Lectures_on_Matrices_of_Graphs.pdf

edited by
23 votes
23 votes

Using these quick observations we see that option (A) the correct answer.

3 votes
3 votes
From the definition of adjacency matrix of G2, it is clear that any two vertices that were adjacent in G are also adjacent in G2. Also, for any two vertices m, n of G which were not adjacent in G will be adjacent in G2 iff they are adjacent to some other common vertex(just try to find the value of N(m, n) for some m, n. You will see why this  double implication is true).

Also, take any path between any two vertex, say x and y in G. Let the vertices along this path be x, x1, x2,…, y. Now there will be a new path corresponding to this in G2 which will be x, x2, x4, …, y because of the same reason as discussed above(for eg, in G2 x and x2 will become adjacent as both were adjacent to x1 in G).

So the length of all paths between any 2 vertex will become almost half.
edited by
1 votes
1 votes
$M^{2}$ will be the adjacency matrix of the graph H derived from G as follow:

H(a,b) = 1 iff (there exists a vertex c st. G(a,c) = 1 and G(c,b) = 1)

So basically there is an edge between a,b iff there is some vertex c st. there is an edge (a,c) and an edge (c,b) in G. When we do $G \cup H$ in the resulting graph diameter reduces to 0.5 of the origibal graph
Answer:

Related questions

13 votes
13 votes
5 answers
1
Arjun asked Feb 18, 2021
8,018 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,832 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...