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, $\frac{1}{\left(2^{n-1}\right)}$ $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$ Graph Theory gateit-2006 graph-theory graph-coloring normal + – Ishrat Jahan asked Oct 31, 2014 edited Nov 21, 2017 by pavan singh Ishrat Jahan 13.1k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Chhotu commented Sep 19, 2017 i edited by Chhotu Nov 16, 2017 reply Follow Share 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}$. 15 votes 15 votes set2018 commented Nov 12, 2017 reply Follow Share how u calculate diameter of graph? The diameter of a graph is the length of the shortest path between the most distanced nodes 5 votes 5 votes Hemant Parihar commented Jan 15, 2018 reply Follow Share @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. 6 votes 6 votes JashanArora commented Feb 28, 2020 reply Follow Share set2018 $diameter = max(eccentricity(v), v \ \epsilon \ G)$ 1 votes 1 votes Please log in or register to add a comment.
Best answer 46 votes 46 votes 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 $\left(n-1\right)$ edges or $'n'$ vertices to get a path b/w two arbitrary points. So ratio is $\left(\frac{2}{n}\right).$ 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 Sandeep_Uniyal answered Jan 19, 2015 edited May 25, 2018 by kenzou Sandeep_Uniyal comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments pritishc commented Jan 7, 2020 reply Follow Share https://math.stackexchange.com/questions/1503130/can-bipartite-graphs-have-isolated-vertices 0 votes 0 votes Ritik gupta commented Jan 27, 2022 reply Follow Share toxic desire,according to your diagram the diameter would be 4 not 3 you missed the edge between 000 and 010 [one bit change ]100 and 110 [one bit change ] if you make these edges then the diameter will be 3 so ans 2/3 0 votes 0 votes JAINchiNMay commented Nov 4, 2022 reply Follow Share For example let’s take a 3-bit string then 000→ 001 → 011→ 111 we would require 3 edges So in general diameter will be n ,not (n-1) correct me If i am wrong 0 votes 0 votes Please log in or register to add a comment.
31 votes 31 votes Eccentricity is we have to traverse max distance using optimal path (i.e by using min vetrices) Max. Eccentricity (i.e Diameter) here is 3, as we can start from any vertex say (000) and to reach vertex (111) diameter is 3. Hence, the ratio 2/n. n is here 3 i.e length of bit string Kuljeet Shan answered Mar 20, 2019 Kuljeet Shan comment Share Follow See all 0 reply Please log in or register to add a comment.
14 votes 14 votes Answer better explained here :https://gateoverflow.in/38185/haming-distance-and-chromatic-number pC answered May 9, 2016 pC comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes (ans c) It can be easily solved by putting the value of n=1. I.e, we have to node '0' and '1'. And they are connected with an edge. Here C.N. is 2 and diameter is 1. So ratio is 2. Now put n=1 in option and check whether answer is 2 or not. Ritik Jain RJ answered Sep 25, 2018 Ritik Jain RJ comment Share Follow See 1 comment See all 1 1 comment reply Souvik33 commented Dec 5, 2022 reply Follow Share @Ritik Jain RJ What an idea sirji 😅🙏 0 votes 0 votes Please log in or register to add a comment.