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.0k 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 Himanshu1 commented Feb 2, 2016 reply Follow Share for traversing from 000. . .0 ⟶ 111. . .1 , we require to traverse atleast 'n' edges. 16 votes 16 votes Dulqar commented Jan 2, 2017 reply Follow Share How to find diameyer of the graph ? 0 votes 0 votes kumar_sanjay commented Jan 26, 2017 reply Follow Share 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) 0 votes 0 votes rishi71662data4 commented Nov 4, 2017 reply Follow Share To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph. 10 votes 10 votes akankshadewangan24 commented Feb 13, 2018 reply Follow Share Plz explain it through diagram or some derivative solution????? M confused 0 votes 0 votes smsubham commented Apr 14, 2018 reply Follow Share Link to the MIT page in answer: http://web.archive.org/web/20100715032114/https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf 2 votes 2 votes shraddha priya commented Sep 11, 2018 reply Follow Share How to draw K-map here? Can You show it please... 0 votes 0 votes Sourav Basu commented Oct 27, 2018 reply Follow Share https://math.stackexchange.com/questions/301562/prove-n-cube-is-bipartite 0 votes 0 votes paraskk commented Aug 22, 2019 reply Follow Share How did we conclude this is BIPARTITE ?? How to coclude if ANY graph is bipartitte ?? 0 votes 0 votes toxicdesire commented Oct 29, 2019 reply Follow Share People who are wondering why the resultant K-map will be bipartite, here's how. 9 votes 9 votes pritishc commented Jan 7, 2020 reply Follow Share Every 2-chromatic graph is known to be bipartite. Converse holds except a particular case - every bipartite graph except graphs of 2 or more isolated nodes (no edges whatsoever) is 2-chromatic. 0 votes 0 votes toxicdesire commented Jan 7, 2020 reply Follow Share Pritish, Are there bipartite graphs with more than two isolated vertices? 0 votes 0 votes 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.