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

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 2

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

Answer 3

We can divide the nodes of the graph into two disjoint sets A and B, such that there is no edge between the vertices within a set.

Say bit string length is 3, then total vertices = 8.

Include vertex 000 into set A and include vertex 001 into set B,

Now include vertex V into set A, if the Hamming distance between V and 000 is even.

Same way include vertex V into set B, if the Hamming distance between V and 001 is even.

Now Set A = {000,011,110,101}

Set B = {001,111,100,010}

It makes sure there is no edge between the vertices within a set(because every pair of vertices in a set has an even hamming distance)

So every Bipartite graph can be colored with 2 colors.

And the shortest distance between every pair of vertices is the hamming distance between the vertices.

And the largest of such distance i.e diameter is between 000 and 111.

So the diameter of the graph is N.

 

It’s indeed an N-Cube graph containing 2^N vertices.

More about the N-Cube graph :

N-Cube graph is bipartite and can be colored with 2 colors.

The degree of each vertex is N(i.e total vertices having the hamming distance of 1 with the respective vertex)

The diameter of an N-Cube graph is N.

PS : You can relate the N-Cube graph with the concept of Boolean Algebra in Group theory.

Answer 4

This graph is hypercube graph (Qn).

The graph is bipartite because we can seperate the given strings in such a way that all bits with even parity comes under one set and all the odd parity bits into other set . So , automatically you know that if a graph is bipartite then it is 2 colourable ( Assign same colour to the every vertex in the same set(partition)).

And second thing is to know about the diameter , diameter is the longest distance among all the shortest paths between two vertices .Here the diameter is indirectly refers to the max distance (Hamming distance between two bits ) . As you know that Hamming distance in worst case occurs when bits in one strings is complement to another , so maximum diameter in the given graph is n (if n is the noof bits. Ex 000 and 111 the diameter is 3) .

 

So chromatic number of graph Qn is 2 and Max distance is n .

 

So, option C is correct