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

  0 ----------------1                  

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

The diameter of a graph is the length of the shortest path between the most distanced nodes  = 0 to 1 which is equal to 1  

therefore  ratio= 2/1=2

 only Option C is TRUE