edited by
13,062 views
64 votes
64 votes

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,

  1. $\frac{1}{\left(2^{n-1}\right)}$
  2. $\left(\frac{1}{n}\right)$
  3. $\left(\frac{2}{n}\right)$
  4. $\left(\frac{3}{n}\right)$
edited by

9 Answers

1 votes
1 votes

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.

0 votes
0 votes
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
0 votes
0 votes
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.
0 votes
0 votes
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
Answer:

Related questions

37 votes
37 votes
7 answers
1
Ishrat Jahan asked Oct 31, 2014
8,726 views
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...
34 votes
34 votes
4 answers
2
Ishrat Jahan asked Oct 27, 2014
8,185 views
What is the chromatic number of the following graph? $2$$3$$4$$5$
43 votes
43 votes
4 answers
3
Akash Kanase asked Feb 12, 2016
15,329 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
46 votes
46 votes
6 answers
4
Kathleen asked Sep 15, 2014
11,058 views
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...