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

After reading this question words "Gray code", "Hypercube graph", "Haming Distance" and "Even length cycles"  are  coming in mind.

Now if you are thinking why Hypercube graph has chromatic no = 2  or Even length cycle then refer -->

https://math.stackexchange.com/questions/227681/how-to-find-chromatic-number-of-the-hypercube-q-n

Chromatic number is 2 so maximum independent set size is $2^{n-1}$.

---

how u calculate diameter of graph?

The diameter of a graph is the length of the shortest path between the most distanced nodes

---

@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)$

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

https://math.stackexchange.com/questions/1503130/can-bipartite-graphs-have-isolated-vertices

---

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

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 😅🙏