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
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 (n-1) edges or 'n' vertices to get a path b/w two arbitrary points.
So ratio is 2/n.
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
for traversing from 000. . .0 ⟶ 111. . .1 , we require to traverse atleast 'n' edges.
3308 Points
1884 Points
1656 Points
1640 Points
1396 Points
1272 Points
1162 Points
1048 Points
1010 Points
754 Points
742 Points
510 Points
490 Points
304 Points
248 Points
Gatecse