GATE CSE
First time here? Checkout the FAQ!
x
0 votes
34 views
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?
asked in Graph Theory by Active (2.4k points)   | 34 views

The definition itself says Simple graph it can't have self loops

Simple graph: No self loop & No Multiedges between 2 vertices

Multi graph: Can have multieedges between 2 vertices but no self loop

General graph or Pseudograph: Can have both

But it was not mentioned that complement graph of simple graph has to be simple.
They are talking about 2 adjacent vertices,if there was and edge in G then it can't be there in G' .So if we take 2 vertices v1 and v2 ,if there were an edge between them in G it shouldn't be there in G'

Moreover when you do G U G' you should get complete graph. Even complete graph can't have self loop
Got it .thanks:)

Please log in or register to answer this question.

Top Users Jan 2017
  1. Debashish Deka

    7906 Points

  2. Habibkhan

    4736 Points

  3. Vijay Thakur

    4474 Points

  4. sudsho

    4318 Points

  5. saurabh rai

    4200 Points

  6. Arjun

    3638 Points

  7. Bikram

    3500 Points

  8. santhoshdevulapally

    3480 Points

  9. GateSet

    3228 Points

  10. Sushant Gokhale

    3116 Points

Monthly Topper: Rs. 500 gift card

18,944 questions
23,897 answers
52,122 comments
20,213 users