GATE CSE
First time here? Checkout the FAQ!
x
0 votes
54 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 Veteran (15k points) 12 109 315 | 54 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.



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
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8280 Points

  4. srestha

    6300 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3970 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Commentator Shivam Chauhan
Notable Question set2018
Nice Comment srestha
Notable Question set2018
Regular Shankar Jha
Popular Question Shubhanshu
Good Comment mcjoshi
Notable Question antarachoudhury
Popular Question shweta12345
Good Comment Rohan Mundhey
27,325 questions
35,176 answers
84,122 comments
33,280 users