The Gateway to Computer Science Excellence
+15 votes
1.1k views
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
closed as a duplicate of: GATE2006-IT-25
in Graph Theory by Boss (21.3k points)
retagged by | 1.1k views
0
@sourav_anand ans given as 2/5 . it might be wrong also. pls explain your approach
Thx in advance

1 Answer

+29 votes
Best answer
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
by Boss (16.1k points)
edited by
+6

n=3 bits

0
http://mathworld.wolfram.com/GraphDiameter.html

Diameter how can be 5????. It should be 3...
0
obviously diameter will be three but here n= 3 bits and i have written it 5 for n=5..u make the graph of 5 bits u will get [email protected]
+1
@sourav_anad how did u visualize it as cube ?

According to ur picture for 3 bit length
would the ratio be 2/3 ?
+5
yes...for n= 3 bit ratio =2/3 and for n=5 bit ratio=2/5;
0
For n=2, the ratio is coming as 2/n as for 2 bits hamming distance is not equal to 2.

What would be answer for n=2?
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,523 answers
195,611 comments
101,287 users