GATE CSE
First time here? Checkout the FAQ!
x
0 votes
39 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 Loyal (3.1k points)   | 39 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 Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2606 Points

  5. Debashish Deka

    2092 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1318 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1166 Points

  10. Sanjay Sharma

    1004 Points

Monthly Topper: Rs. 500 gift card

21,439 questions
26,753 answers
60,919 comments
22,929 users