20:
50:
For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.
423:
628:
247:
561:
466:
From the definition which uses repeated addition of vertices, one can derive an alternative way of uniquely describing a threshold graph, by means of a string of symbols.
345:
587:
657:. All these relations can be explained in terms of their characterisation by forbidden induced subgraphs. A cograph is a graph with no induced path on four vertices, P
484:
319:
144:
170:
193:
528:
504:
365:
290:
270:
115:
92:
649:. A graph is a threshold graph if and only if it is both a cograph and a split graph. Every graph that is both a trivially perfect graph and the
681:
is its complement, that is, two disjoint edges. This also explains why threshold graphs are closed under taking complements; the P
799:(1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.),
486:
is always the first character of the string, and represents the first vertex of the graph. Every subsequent character is either
35:
is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:
703:
showed that threshold graphs can be recognized in linear time; if a graph is not threshold, an obstruction (one of P
439:
374:
368:
196:
592:
729:
202:
74:
An equivalent definition is the following: a graph is a threshold graph if there are a real number
537:
324:
894:
889:
809:
646:
566:
455:
252:
Another equivalent definition is this: a graph is a threshold graph if there are a real number
653:
of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of
469:
95:
849:
295:
120:
8:
803:, Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162
792:
149:
175:
724:
513:
489:
350:
275:
255:
100:
77:
753:
775:
770:
43:
765:
650:
589:
represents a path on three vertices. The graph of the figure can be represented as
443:
873:
845:
830:
826:
796:
442:: A graph is a threshold graph if and only if it no four of its vertices form an
831:"Linear-time certifying recognition algorithms and forbidden induced subgraphs"
654:
883:
779:
752:
Reiterman, Jan; Rödl, Vojtěch; Šiňajová, Edita; Tůma, Miroslav (1985-04-01).
46:
to the graph, i.e. a single vertex that is connected to all other vertices.
28:
642:
451:
447:
431:
is the "threshold" for the property of being an edge, or equivalently
19:
638:
632:
876:, Information System on Graph Classes and their Inclusions.
751:
427:
The name "threshold graph" comes from these definitions:
801:
Studies in
Integer Programming (Proc. Worksh. Bonn 1975)
530:, which denotes the addition of a dominating vertex (or
506:, which denotes the addition of an isolated vertex (or
595:
569:
540:
516:
492:
472:
377:
353:
327:
298:
278:
258:
205:
178:
152:
123:
103:
80:
16:
Graph formed by adding isolated or universal vertices
661:, and a threshold graph is a graph with no induced P
622:
581:
555:
522:
498:
478:
417:
359:
339:
313:
284:
264:
241:
187:
164:
138:
109:
86:
39:Addition of a single isolated vertex to the graph.
563:represents a star graph with three leaves, while
881:
825:
700:
818:. 2nd edition, Annals of Discrete Mathematics,
791:
55:
856:
685:is self-complementary, hence if a graph is P
63:
814:Algorithmic Graph Theory and Perfect Graphs
58:. A chapter on threshold graphs appears in
69:
54:Threshold graphs were first introduced by
857:Mahadev, N. V. R.; Peled, Uri N. (1995),
769:
633:Related classes of graphs and recognition
418:{\displaystyle \sum _{v\in X}a(v)\leq T.}
808:
435:is the threshold for being independent.
59:
18:
637:Threshold graphs are a special case of
882:
859:Threshold Graphs and Related Topics
13:
697:-free, its complement is as well.
677:is a cycle of four vertices and 2K
14:
906:
867:
534:vertex). For example, the string
623:{\displaystyle \epsilon uuujuuj}
461:
440:forbidden graph characterization
23:An example of a threshold graph.
146:such that for any two vertices
745:
701:Heggernes & Kratsch (2007)
403:
397:
308:
302:
242:{\displaystyle w(u)+w(v)>S}
230:
224:
215:
209:
133:
127:
1:
738:
438:Threshold graphs also have a
321:such that for any vertex set
771:10.1016/0012-365X(85)90080-9
556:{\displaystyle \epsilon uuj}
340:{\displaystyle X\subseteq V}
7:
838:Nordic Journal of Computing
718:
582:{\displaystyle \epsilon uj}
56:Chvátal & Hammer (1977)
10:
911:
829:; Kratsch, Dieter (2007),
816:, New York: Academic Press
64:Mahadev & Peled (1995)
479:{\displaystyle \epsilon }
810:Golumbic, Martin Charles
647:trivially perfect graphs
754:"Threshold hypergraphs"
70:Alternative definitions
844:(1–2): 87–108 (2008),
624:
583:
557:
524:
500:
480:
419:
361:
341:
315:
286:
266:
243:
189:
166:
140:
111:
88:
24:
734:Threshold hypergraphs
730:Series–parallel graph
625:
584:
558:
525:
501:
481:
446:that is a three-edge
420:
362:
342:
316:
292:a real vertex weight
287:
267:
244:
190:
167:
141:
117:a real vertex weight
112:
89:
42:Addition of a single
22:
758:Discrete Mathematics
593:
567:
538:
514:
490:
470:
375:
351:
325:
314:{\displaystyle a(v)}
296:
276:
272:and for each vertex
256:
203:
176:
150:
139:{\displaystyle w(v)}
121:
101:
78:
66:is devoted to them.
651:complementary graph
165:{\displaystyle v,u}
725:Indifference graph
715:) will be output.
620:
579:
553:
520:
496:
476:
415:
393:
357:
337:
311:
282:
262:
239:
188:{\displaystyle uv}
185:
162:
136:
107:
84:
25:
822:, Elsevier, 2004.
523:{\displaystyle j}
499:{\displaystyle u}
378:
360:{\displaystyle X}
285:{\displaystyle v}
265:{\displaystyle T}
110:{\displaystyle v}
87:{\displaystyle S}
44:dominating vertex
902:
874:Threshold graphs
862:
852:
835:
827:Heggernes, Pinar
817:
804:
797:Hammer, Peter L.
784:
783:
773:
749:
629:
627:
626:
621:
588:
586:
585:
580:
562:
560:
559:
554:
529:
527:
526:
521:
505:
503:
502:
497:
485:
483:
482:
477:
454:, or a two-edge
444:induced subgraph
424:
422:
421:
416:
392:
366:
364:
363:
358:
346:
344:
343:
338:
320:
318:
317:
312:
291:
289:
288:
283:
271:
269:
268:
263:
248:
246:
245:
240:
194:
192:
191:
186:
171:
169:
168:
163:
145:
143:
142:
137:
116:
114:
113:
108:
93:
91:
90:
85:
910:
909:
905:
904:
903:
901:
900:
899:
880:
879:
870:
833:
793:Chvátal, Václav
788:
787:
750:
746:
741:
721:
714:
710:
706:
696:
692:
688:
684:
680:
676:
672:
668:
664:
660:
655:interval graphs
635:
594:
591:
590:
568:
565:
564:
539:
536:
535:
515:
512:
511:
491:
488:
487:
471:
468:
467:
464:
382:
376:
373:
372:
371:if and only if
352:
349:
348:
326:
323:
322:
297:
294:
293:
277:
274:
273:
257:
254:
253:
204:
201:
200:
199:if and only if
177:
174:
173:
151:
148:
147:
122:
119:
118:
102:
99:
98:
79:
76:
75:
72:
62:, and the book
60:Golumbic (1980)
33:threshold graph
17:
12:
11:
5:
908:
898:
897:
895:Perfect graphs
892:
890:Graph families
878:
877:
869:
868:External links
866:
865:
864:
854:
823:
806:
786:
785:
764:(2): 193–200.
743:
742:
740:
737:
736:
735:
732:
727:
720:
717:
712:
708:
704:
694:
690:
686:
682:
678:
674:
670:
666:
662:
658:
634:
631:
619:
616:
613:
610:
607:
604:
601:
598:
578:
575:
572:
552:
549:
546:
543:
519:
495:
475:
463:
460:
450:, a four-edge
414:
411:
408:
405:
402:
399:
396:
391:
388:
385:
381:
356:
336:
333:
330:
310:
307:
304:
301:
281:
261:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
184:
181:
161:
158:
155:
135:
132:
129:
126:
106:
83:
71:
68:
48:
47:
40:
15:
9:
6:
4:
3:
2:
907:
896:
893:
891:
888:
887:
885:
875:
872:
871:
860:
855:
851:
847:
843:
839:
832:
828:
824:
821:
815:
811:
807:
802:
798:
794:
790:
789:
781:
777:
772:
767:
763:
759:
755:
748:
744:
733:
731:
728:
726:
723:
722:
716:
702:
698:
656:
652:
648:
644:
640:
630:
617:
614:
611:
608:
605:
602:
599:
596:
576:
573:
570:
550:
547:
544:
541:
533:
517:
509:
493:
473:
462:Decomposition
459:
457:
453:
449:
445:
441:
436:
434:
430:
425:
412:
409:
406:
400:
394:
389:
386:
383:
379:
370:
354:
334:
331:
328:
305:
299:
279:
259:
250:
236:
233:
227:
221:
218:
212:
206:
198:
182:
179:
159:
156:
153:
130:
124:
104:
97:
94:and for each
81:
67:
65:
61:
57:
52:
45:
41:
38:
37:
36:
34:
30:
21:
858:
841:
837:
819:
813:
800:
761:
757:
747:
699:
643:split graphs
636:
531:
510:vertex), or
507:
465:
437:
432:
428:
426:
251:
73:
53:
49:
32:
29:graph theory
26:
452:cycle graph
369:independent
884:Categories
861:, Elsevier
739:References
448:path graph
780:0012-365X
597:ϵ
571:ϵ
542:ϵ
474:ϵ
407:≤
387:∈
380:∑
332:⊆
812:(1980),
719:See also
693:- and 2K
639:cographs
456:matching
850:2460558
711:, or 2K
848:
778:
669:nor 2K
645:, and
195:is an
96:vertex
834:(PDF)
508:union
776:ISSN
689:-, C
673:. C
532:join
234:>
197:edge
31:, a
766:doi
707:, C
665:, C
367:is
249:.
27:In
886::
846:MR
842:14
840:,
836:,
820:57
795:;
774:.
762:54
760:.
756:.
641:,
458:.
347:,
172:,
863:.
853:.
805:.
782:.
768::
713:2
709:4
705:4
695:2
691:4
687:4
683:4
679:2
675:4
671:2
667:4
663:4
659:4
618:j
615:u
612:u
609:j
606:u
603:u
600:u
577:j
574:u
551:j
548:u
545:u
518:j
494:u
433:T
429:S
413:.
410:T
404:)
401:v
398:(
395:a
390:X
384:v
355:X
335:V
329:X
309:)
306:v
303:(
300:a
280:v
260:T
237:S
231:)
228:v
225:(
222:w
219:+
216:)
213:u
210:(
207:w
183:v
180:u
160:u
157:,
154:v
134:)
131:v
128:(
125:w
105:v
82:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
