301:
20:
402:(one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an
362:
and complementation operations. They form a self-complementary family of graphs: the complement of any cograph is another different cograph. For cographs of more than one vertex, exactly one graph in each complementary pair is connected, and one equivalent definition of cographs is that each of their
414:
on the complement graph, in an amount of time that is linear in the size of the given graph, even when the complement graph may have a much larger size. It is also possible to use these simulations to compute other properties concerning the connectivity of the complement graph.
227:, and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self-loops would result in a graph with self-loops on all vertices.
273:
in the complement graph and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph.
374:, the graphs in which the vertices can be partitioned into a clique and an independent set. The same partition gives an independent set and a clique in the complement graph.
367:
has a disconnected complement. Another, self-complementary definition is that they are the graphs with no induced subgraph in the form of a four-vertex path.
333:
Several classes of graphs are self-complementary, in the sense that the complement of any graph in one of these classes is another graph in the same class.
200:
of the same number of vertices (i.e. all entries are unity except the diagonal entries which are zero), then the adjacency matrix of the complement of
385:(adjacent to all previously-added vertices). These two operations are complementary and they generate a self-complementary class of graphs.
406:
representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either
692:
Ito, Hiro; Yokoyama, Mitsuo (1998), "Linear time algorithms for graph search and connectivity determination on complement graphs",
173:, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element
630:
485:
456:
477:
694:
547:
266:
344:
equals the size of the maximum clique. The fact that the complement of a perfect graph is also perfect is the
581:
509:
48:
523:, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171,
773:
381:
are the graphs formed by repeatedly adding either an independent vertex (one with no neighbors) or a
315:
309:
618:
86:
395:
448:
442:
398:
on graphs, the distinction between a graph and its complement is an important one, because a
345:
270:
59:
542:
349:
754:
715:
675:
640:
604:
528:
513:
411:
733:(1999), "Simple and efficient graph compression schemes for dense and complement graphs",
8:
284:
216:
158:
75:
407:
277:
707:
654:
Golumbic, Martin
Charles; Jamison, Robert E. (2006), "Rank-tolerance graph classes",
626:
595:
561:
481:
452:
434:
319:
742:
703:
663:
590:
556:
505:
382:
364:
341:
251:
186:
750:
711:
671:
636:
600:
524:
378:
288:
235:
Several graph-theoretic concepts are related to each other via complementation:
730:
438:
403:
359:
244:
240:
223:
may be defined by adding a self-loop to every vertex that does not have one in
197:
170:
79:
74:. That is, to generate the complement of a graph, one fills in all the missing
67:
24:
746:
300:
767:
576:
492:
337:
579:; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs",
19:
399:
174:
113:
36:
32:
371:
327:
358:
are defined as the graphs that can be built up from single vertices by
323:
212:
667:
330:. There is no known characterization of self-complementary graphs.
355:
545:(1972a), "Normal hypergraphs and the perfect graph conjecture",
575:
295:
280:
group of a graph is the automorphism group of its complement.
370:
Another self-complementary class of graphs is the class of
258:
is the complement of the corresponding induced subgraph in
340:
are the graphs in which, for every induced subgraph, the
82:, and removes all the edges that were previously there.
16:
Graph with same nodes but opposite connections as another
322:
to its own complement. Examples include the four-vertex
27:(on the left) and its complement graph (on the right).
728:
504:
219:(but not multiple adjacencies) the complement of
765:
653:
89:of the graph; only the edges are complemented.
625:, Academic Press, Theorem 6.1, p. 150,
230:
691:
623:Algorithmic Graph Theory and Perfect Graphs
304:The four-vertex path is self-complementary.
296:Self-complementary graphs and graph classes
433:
594:
560:
617:
299:
18:
541:
471:
766:
687:
685:
389:
185:in the formula above. In terms of the
735:Journal of Combinatorial Optimization
729:Kao, Ming-Yang; Occhiogrosso, Neill;
429:
427:
120:consist of all 2-element subsets of
682:
514:"The structure of claw-free graphs"
291:, although the reverse is not true.
254:of the complement graph of a graph
62:such that two distinct vertices of
13:
211:The complement is not defined for
14:
785:
424:
196:is the adjacency matrix of the
722:
695:Information Processing Letters
647:
611:
569:
535:
498:
465:
444:Graph Theory with Applications
1:
708:10.1016/S0020-0190(98)00071-4
521:Surveys in combinatorics 2005
418:
92:
596:10.1016/0166-218X(81)90013-5
582:Discrete Applied Mathematics
562:10.1016/0012-365X(72)90006-4
7:
10:
790:
472:Diestel, Reinhard (2005),
307:
85:The complement is not the
447:, North-Holland, p.
231:Applications and examples
70:they are not adjacent in
619:Golumbic, Martin Charles
316:self-complementary graph
310:Self-complementary graph
283:The complement of every
747:10.1023/A:1009720402326
656:Journal of Graph Theory
215:. In graphs that allow
396:analysis of algorithms
305:
28:
346:perfect graph theorem
303:
239:The complement of an
143:is the complement of
22:
548:Discrete Mathematics
412:breadth-first search
181:in place of the set
390:Algorithmic aspects
318:is a graph that is
285:triangle-free graph
159:relative complement
78:required to form a
493:Electronic edition
435:Bondy, John Adrian
408:depth-first search
306:
29:
668:10.1002/jgt.20163
506:Chudnovsky, Maria
365:induced subgraphs
192:of the graph, if
781:
774:Graph operations
759:
757:
726:
720:
718:
689:
680:
678:
651:
645:
643:
615:
609:
607:
598:
573:
567:
565:
564:
539:
533:
531:
518:
502:
496:
490:
476:(3rd ed.),
469:
463:
461:
431:
383:universal vertex
379:threshold graphs
342:chromatic number
326:and five-vertex
269:in a graph is a
261:
257:
252:induced subgraph
226:
222:
187:adjacency matrix
184:
180:
168:
164:
156:
146:
142:
123:
119:
111:
73:
65:
57:
53:
789:
788:
784:
783:
782:
780:
779:
778:
764:
763:
762:
731:Teng, Shang-Hua
727:
723:
690:
683:
652:
648:
633:
616:
612:
574:
570:
540:
536:
516:
503:
499:
488:
470:
466:
459:
439:Murty, U. S. R.
432:
425:
421:
392:
312:
298:
289:claw-free graph
267:independent set
259:
255:
247:and vice versa.
233:
224:
220:
182:
178:
171:directed graphs
166:
162:
148:
144:
125:
121:
117:
98:
95:
71:
63:
55:
51:
17:
12:
11:
5:
787:
777:
776:
761:
760:
741:(4): 351–359,
721:
702:(4): 209–213,
681:
662:(4): 317–340,
646:
631:
610:
589:(3): 163–174,
577:Corneil, D. G.
568:
555:(3): 253–267,
543:Lovász, László
534:
497:
486:
464:
457:
422:
420:
417:
404:implicit graph
391:
388:
387:
386:
375:
368:
360:disjoint union
353:
338:Perfect graphs
308:Main article:
297:
294:
293:
292:
281:
274:
263:
248:
245:complete graph
241:edgeless graph
232:
229:
198:complete graph
129: = (
102: = (
94:
91:
87:set complement
80:complete graph
68:if and only if
25:Petersen graph
15:
9:
6:
4:
3:
2:
786:
775:
772:
771:
769:
756:
752:
748:
744:
740:
736:
732:
725:
717:
713:
709:
705:
701:
697:
696:
688:
686:
677:
673:
669:
665:
661:
657:
650:
642:
638:
634:
632:0-12-289260-7
628:
624:
620:
614:
606:
602:
597:
592:
588:
584:
583:
578:
572:
563:
558:
554:
550:
549:
544:
538:
530:
526:
522:
515:
511:
510:Seymour, Paul
507:
501:
494:
489:
487:3-540-26182-6
483:
479:
475:
468:
460:
458:0-444-19451-7
454:
450:
446:
445:
440:
436:
430:
428:
423:
416:
413:
409:
405:
401:
397:
384:
380:
376:
373:
369:
366:
361:
357:
354:
351:
350:László Lovász
347:
343:
339:
336:
335:
334:
331:
329:
325:
321:
317:
311:
302:
290:
286:
282:
279:
275:
272:
268:
264:
253:
249:
246:
242:
238:
237:
236:
228:
218:
214:
209:
207:
203:
199:
195:
191:
188:
176:
175:ordered pairs
172:
160:
155:
152: \
151:
140:
137: \
136:
132:
128:
115:
109:
105:
101:
90:
88:
83:
81:
77:
69:
66:are adjacent
61:
50:
46:
42:
38:
34:
26:
21:
738:
734:
724:
699:
693:
659:
655:
649:
622:
613:
586:
580:
571:
552:
546:
537:
520:
500:
474:Graph Theory
473:
467:
443:
400:sparse graph
393:
372:split graphs
332:
313:
278:automorphism
234:
210:
205:
201:
193:
189:
153:
149:
138:
134:
130:
126:
114:simple graph
107:
103:
99:
96:
84:
58:on the same
44:
40:
37:graph theory
33:mathematical
30:
328:cycle graph
213:multigraphs
54:is a graph
419:References
363:connected
324:path graph
320:isomorphic
217:self-loops
93:Definition
41:complement
495:, page 4.
35:field of
768:Category
621:(1980),
512:(2005),
478:Springer
441:(1976),
356:Cographs
147:, where
116:and let
60:vertices
755:1669307
716:1629714
676:2242832
641:0562306
605:0619603
529:2187738
394:In the
157:is the
133:,
124:. Then
106:,
45:inverse
31:In the
753:
714:
674:
639:
629:
603:
527:
484:
455:
271:clique
169:. For
39:, the
517:(PDF)
287:is a
243:is a
112:be a
76:edges
49:graph
47:of a
627:ISBN
482:ISBN
453:ISBN
377:The
276:The
250:Any
97:Let
23:The
743:doi
704:doi
664:doi
591:doi
557:doi
410:or
348:of
265:An
206:Q-A
204:is
177:of
165:in
161:of
43:or
770::
751:MR
749:,
737:,
712:MR
710:,
700:66
698:,
684:^
672:MR
670:,
660:52
658:,
637:MR
635:,
601:MR
599:,
585:,
551:,
525:MR
519:,
508:;
491:.
480:,
451:,
437:;
426:^
314:A
208:.
758:.
745::
739:2
719:.
706::
679:.
666::
644:.
608:.
593::
587:3
566:.
559::
553:2
532:.
462:.
449:6
352:.
262:.
260:G
256:G
225:G
221:G
202:A
194:Q
190:A
183:K
179:V
167:K
163:E
154:E
150:K
145:G
141:)
139:E
135:K
131:V
127:H
122:V
118:K
110:)
108:E
104:V
100:G
72:G
64:H
56:H
52:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
