GATE IT 2006 | Question: 25

Question

Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit). The ratio of the chromatic number of $G$ to the diameter of $G$ is,

• A. $\frac{1}{\left(2^{n-1}\right)}$
• B. $\left(\frac{1}{n}\right)$
• C. $\left(\frac{2}{n}\right)$
• D. $\left(\frac{3}{n}\right)$

Comments

@set2018,

For the diameter, the bit difference (Hamming distance) between the two nodes should be maximum.

For example: For n = 3,  000  $\rightarrow$ 001  $\rightarrow$  011  $\rightarrow$ 111.

---

set2018 $diameter = max(eccentricity(v), v \  \epsilon \ G)$

---

It's bipartite on sets {even sum} and {odd sum}
Diamete is n because, complemented vertices are the farthest apart.
In order to reach from one complemented vertex to another we can flip one bit at a time, hence flipping n bits is equivalent to taking n edges.

X = 2, Diameter = n
2/n

Answer 1

Answer is (C)

For the given condition we can simply design a K-MAP and mark an edge between every two adjacent cells in K-Map. (adjacency has to seen just as we do for minimization )

That will give us a Bipartite graph. chromatic number for this $=2$.

Also from the same we can conclude that we need ,for a $'n'$ bit string, to traverse NO MORE than $\left(n-1\right)$ edges or $'n'$ vertices to get a path b/w two arbitrary points.

So ratio is $\left(\frac{2}{n}\right).$

The given graph is actually hypercubegraph. 

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

See problem 4 here:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf

Comments

toxic desire,

according to your diagram the diameter would be 4 not 3 you missed the edge between 

1. 000 and 010 [one bit change ]
2. 100 and 110 [one bit change ]  if you make these edges then the diameter will be 3 so ans 2/3

---

For example let’s take a 3-bit string  
then 000→ 001 → 011→ 111 we would require 3 edges
So in general diameter will be n ,not (n-1)
correct me If i am wrong

---

@paraskk if the graph doesn't have odd length cycles then it is bipartite graph

Answer 2

Eccentricity is we have to traverse max distance using optimal path (i.e by using min vetrices)

Max. Eccentricity (i.e Diameter) here is 3, as we can start from any vertex say (000) and to reach vertex (111) diameter is 3.

Hence, the ratio 2/n.

n is here 3 i.e length of bit string

 

Answer 3

Answer better explained here :https://gateoverflow.in/38185/haming-distance-and-chromatic-number

Answer 4

(ans c)

It can be easily solved by putting the value of n=1.

I.e, we have to node '0' and '1'. And they are connected with an edge. Here C.N. is 2 and diameter is 1. So ratio is 2.

Now put n=1 in option and check whether answer is 2 or not.

Comments

@Ritik Jain RJ What an idea sirji 😅🙏

---

Oscar winning answer.

 

Answer 5

Simpler Way:-

Lets take $n = 2$. So we have $2^2 = 4$ bit strings = ${00,01,10,11}$

Now it’s given “We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit)”. So here will be edge from $00$ to $01$, $00$ to $10$, $01$ to $11$ and $11$ to $10$. So the Graph will look like this:-

We can see that only 2 colours are enough to colour it. Hence Chromatic number of this graph is $2$.

Now, if we try to find the diameter of the graph {max(smallest distance between any pair of vertices)}. We get the diameter also as $2$. 

Thus, the ratio of the chromatic number of $G$ to the diameter of $G$ is = $2/2 = 1$.

Looking at the options only Option C is TRUE.

Answer 6

answer would be 2/n as it would be hypercube and its chromatic number would be 2 and diameter that is max distance between two vertices would be n