edited by
512 views
0 votes
0 votes
The complementary graph G'  of a simple graph G has the same vertices as G. Two vertices are adjacent in G'  if and only if they are not adjacent in G. Define Qn' (Hypercube complement).

Answer given :-The graph whose vertices are bit strings of length n and two vertices are adjacent if the bit string represented by them differe by more than one bit.

I want to understand that whether the complement graph will have self loops?Because the answer given doesn't consider self loops.I mean why are we not considering the bit strings that are differing by 0 bit,as these are also not there in original graph ,so it must be in complementary graph?
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
dd asked Nov 22, 2016
599 views
If G is a simple graph with 15 edges and $\bar G$ has 13 edges, how many vertices does G have?
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
0 votes
0 votes
0 answers
4