reopened by
2,376 views
17 votes
17 votes
Consider the undirected graph G defined as follows. The vertices are bit string of length 5. We have an edge between vertex “a” and vertex “b” iff “a” and “b” differ only in one bit possible (i.e., hamming distance1). What is the ratio of chromatic number of G to the diameter of G?

Model Question : https://gateoverflow.in/3564/gate2006-it_25
reopened by

1 Answer

Best answer
30 votes
30 votes
apply the given condition of connectivity to 2 bits..00==>01==>11==>10==>00

for 3 bits..image in comment box

ACTUALLY IT IS  A N CUBE...

vertex of n cube=n;

degree of n cube=n;

edges of n cube=n*2^(n-1)
chromatic number=2(ALWAYS)
hence chromatic number of the graph=2

now diameter of graph=number of bits =5

thus ratio =2/5
edited by

Related questions

2 votes
2 votes
1 answer
1
2 votes
2 votes
0 answers
2
Parshu gate asked Nov 11, 2017
1,141 views
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
3 votes
3 votes
3 answers
3
rahul sharma 5 asked Jun 12, 2017
1,911 views
What are the chromatic number of following graphs?Answer is 6 and 4 respectively.But i am getting 3 for both.Please someone confirm this?
0 votes
0 votes
1 answer
4
Imarati Gupta asked Jul 7, 2016
1,104 views