GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
647 views

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. 1/(2n-1)
  2. 1/n
  3. 2/n
  4. 3/n
asked in Graph Theory by Veteran (19k points)   | 647 views

3 Answers

+10 votes
Best answer

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

answered by Boss (7.2k points)  
edited by

for traversing from 000. . .0   ⟶  111. . .1   , we require to traverse atleast 'n' edges.

How to find diameyer of the graph ?
Diameter is shortest path of maximum lenght  in between any two vertices of a graph. maximum lenght can occure between any two vertices. for this we can do it by intution or by applying all pair shotest path algorithm(floyed warshall)
+3 votes
answered by Veteran (20.2k points)  
+2 votes
answer C
answered by Veteran (13.3k points)  
Top Users Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users