GATE CSE
First time here? Checkout the FAQ!
x
0 votes
44 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)   | 44 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:)

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users