278:, by repeatedly searching for and removing a simple vertex. If this process eliminates all vertices in the graph, the graph must be strongly chordal; otherwise, if this process finds a subgraph without any more simple vertices, the original graph cannot be strongly chordal. For a strongly chordal graph, the order in which the vertices are removed by this process is a strong perfect elimination ordering.
365:, various NP-complete problems such as Independent Set, Clique, Coloring, Clique Cover, Dominating Set, and Steiner Tree can be solved efficiently for strongly chordal graphs. Graph isomorphism is isomorphism-complete for strongly chordal graphs. Hamiltonian Circuit remains NP-complete for strongly chordal
251:
A graph is strongly chordal if and only if every one of its induced subgraphs has a simple vertex, a vertex whose neighbors have neighborhoods that are linearly ordered by inclusion. Also, a graph is strongly chordal if and only if it is chordal and every cycle of length five or more has a 2-chord
341:. Since powers of strongly chordal graphs are strongly chordal and trees are strongly chordal, it follows that leaf powers are strongly chordal. They form a proper subclass of strongly chordal graphs, which in turn includes the
199:
Strongly chordal graphs may also be characterized as the graphs having a strong perfect elimination ordering, an ordering of the vertices such that the neighbors of any vertex that come later in the ordering form a
281:
Alternative algorithms are now known that can determine whether a graph is strongly chordal and, if so, construct a strong perfect elimination ordering more efficiently, in time
579:
704:
71:
992:
Uehara, R.; Toda, S.; Nagoya, T. (2005), "Graph isomorphism completeness for chordal bipartite and strongly chordal graphs",
971:
946:
863:
838:
787:
729:
659:
633:
605:
329:, the graphs formed from the leaves of a tree by connecting two leaves by an edge when their distance in the tree is at most
994:
915:
815:
1031:
1026:
603:; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers",
349:. In it is shown that interval graphs and the larger class of rooted directed path graphs are leaf powers.
59:
752:
De Caria, P.; McKee, T.A. (2014), "Maxclique and unit disk characterizations of strongly chordal graphs",
888:
263:
201:
55:
688:
654:
628:
600:
574:
362:
256:
43:
932:
727:
Dahlhaus, E.; Manuel, P. D.; Miller, M. (1998), "A characterization of strongly chordal graphs",
676:
657:; Le, Van Bang; Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers",
700:
1003:
980:
955:
924:
897:
872:
847:
824:
796:
771:
761:
738:
668:
642:
614:
588:
86:
28:
886:
Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees",
75:
275:
693:
346:
852:
743:
74:
as the graphs that do not contain an induced cycle of length greater than three or an
1020:
984:
910:
877:
801:
358:
342:
39:
936:
577:; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs",
680:
24:
631:; Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers",
366:
345:
as the 2-leaf powers. Another important subclass of strongly chordal graphs are
20:
960:
619:
1008:
810:
646:
592:
326:
255:
A graph is strongly chordal if and only if each of its induced subgraphs is a
672:
318:
262:
Strongly chordal graphs may also be characterized in terms of the number of
901:
836:
McKee, T. A. (1999), "A new characterization of strongly chordal graphs",
861:
Müller, H. (1996), "Hamiltonian
Circuits in Chordal Bipartite Graphs",
776:
766:
969:
Spinrad, J. (1993), "Doubly lexical ordering of dense 0–1 matrices",
266:
each edge participates in. Yet another characterization is given in.
928:
828:
252:
triangle, a triangle formed by two chords and an edge of the cycle.
785:
Farber, M. (1983), "Characterizations of strongly chordal graphs",
274:
It is possible to determine whether a graph is strongly chordal in
460:
16:
Chordal graph where all cycles of even length have odd chords
699:, SIAM Monographs on Discrete Mathematics and Applications,
537:
944:
Rautenbach, D. (2006), "Some remarks about leaf roots",
526:
448:
436:
420:
404:
384:
171:-sun cannot be strongly chordal, because the cycle
692:
913:(1987), "Three partition refinement algorithms",
813:(1987), "Doubly lexical orderings of matrices",
548:
483:
224:th vertex in the ordering is adjacent to the
8:
62:(>1) apart from each other in the cycle.
510:
1007:
959:
876:
851:
800:
775:
765:
742:
618:
691:; Le, Van Bang; Spinrad, Jeremy (1999),
719:-domination and Graph Covering Problems
514:
377:
357:Since strongly chordal graphs are both
97:vertices, partitioned into two subsets
754:Discussiones Mathematicae Graph Theory
559:
527:Nishimura, Ragde & Thilikos (2002)
494:
432:
416:
400:
506:
472:
396:
7:
580:SIAM Journal on Discrete Mathematics
449:Dahlhaus, Manuel & Miller (1998)
333:. A leaf power is a graph that is a
437:Brandstädt, Le & Spinrad (1999)
421:Brandstädt, Le & Spinrad (1999)
405:Brandstädt, Le & Spinrad (1999)
385:Brandstädt, Le & Spinrad (1999)
248:th vertices must also be adjacent.
240:th vertices are adjacent, then the
72:forbidden subgraph characterization
721:, Ph.D. thesis, Cornell University
54:, i.e., an edge that connects two
14:
549:Uehara, Toda & Nagoya (2005)
317:An important subclass (based on
70:Strongly chordal graphs have a
972:Information Processing Letters
660:ACM Transactions on Algorithms
634:Information Processing Letters
162: + 1) mod
93:-sun is a chordal graph with 2
1:
853:10.1016/S0012-365X(99)00107-7
744:10.1016/S0012-365X(97)00268-9
133:,...}, such that each vertex
995:Discrete Applied Mathematics
985:10.1016/0020-0190(93)90209-R
878:10.1016/0012-365x(95)00057-4
802:10.1016/0012-365X(83)90154-1
484:De Caria & McKee (2014)
144:has exactly two neighbors,
1048:
961:10.1016/j.disc.2006.03.030
620:10.1016/j.disc.2009.10.006
387:, Definition 3.4.1, p. 43.
1009:10.1016/j.dam.2004.06.008
916:SIAM Journal on Computing
816:SIAM Journal on Computing
647:10.1016/j.ipl.2006.01.004
593:10.1137/s0895480193253415
511:Paige & Tarjan (1987)
538:Brandstädt et al. (2010)
461:Brandstädt et al. (1998)
407:, Theorem 7.2.1, p. 112.
204:and such that, for each
46:of even length (≥ 6) in
695:Graph Classes: A Survey
673:10.1145/1435375.1435386
439:, Theorem 5.5.2, p. 78.
423:, Theorem 5.5.1, p. 77.
902:10.1006/jagm.2001.1195
196:... has no odd chord.
85: ≥ 3) as an
889:Journal of Algorithms
714:Chang, G. J. (1982),
463:, Corollary 3, p. 444
363:dually chordal graphs
337:-leaf power for some
232:th vertices, and the
947:Discrete Mathematics
864:Discrete Mathematics
839:Discrete Mathematics
788:Discrete Mathematics
730:Discrete Mathematics
606:Discrete Mathematics
353:Algorithmic problems
257:dually chordal graph
689:Brandstädt, Andreas
655:Brandstädt, Andreas
629:Brandstädt, Andreas
601:Brandstädt, Andreas
575:Brandstädt, Andreas
321:) is the class of
264:complete subgraphs
954:(13): 1456–1461,
767:10.7151/dmgt.1757
301:for a graph with
66:Characterizations
1039:
1012:
1011:
987:
964:
963:
939:
904:
881:
880:
871:(1–3): 291–298,
856:
855:
846:(1–3): 245–247,
831:
805:
804:
795:(2–3): 173–189,
780:
779:
769:
747:
746:
737:(1–3): 269–271,
722:
709:
698:
683:
649:
623:
622:
595:
562:
557:
551:
546:
540:
535:
529:
524:
518:
504:
498:
492:
486:
481:
475:
470:
464:
458:
452:
446:
440:
430:
424:
414:
408:
394:
388:
382:
340:
336:
332:
324:
300:
216: <
212: <
208: <
87:induced subgraph
58:that are an odd
49:
36:strongly chordal
33:
29:undirected graph
1047:
1046:
1042:
1041:
1040:
1038:
1037:
1036:
1017:
1016:
991:
968:
943:
929:10.1137/0216062
908:
885:
860:
835:
829:10.1137/0216057
809:
784:
751:
726:
713:
707:
687:
653:
627:
599:
573:
570:
565:
558:
554:
547:
543:
536:
532:
525:
521:
505:
501:
493:
489:
482:
478:
471:
467:
459:
455:
447:
443:
431:
427:
415:
411:
395:
391:
383:
379:
375:
355:
347:interval graphs
338:
334:
330:
322:
315:
282:
276:polynomial time
272:
195:
189:
183:
177:
166:
152:
138:
132:
125:
114:
107:
68:
47:
31:
17:
12:
11:
5:
1045:
1043:
1035:
1034:
1032:Perfect graphs
1029:
1027:Graph families
1019:
1018:
1015:
1014:
1002:(3): 479–482,
989:
979:(2): 229–235,
966:
941:
923:(6): 973–989,
906:
883:
858:
833:
823:(5): 854–879,
807:
782:
760:(3): 593–602,
749:
724:
711:
705:
685:
667:: Article 11,
651:
641:(4): 133–138,
625:
613:(4): 897–910,
597:
587:(3): 437–455,
569:
566:
564:
563:
552:
541:
530:
519:
515:Spinrad (1993)
499:
487:
476:
465:
453:
441:
425:
409:
389:
376:
374:
371:
359:chordal graphs
354:
351:
343:cluster graphs
314:
311:
271:
268:
193:
187:
181:
175:
157:
148:
136:
130:
123:
119: = {
112:
105:
101: = {
67:
64:
15:
13:
10:
9:
6:
4:
3:
2:
1044:
1033:
1030:
1028:
1025:
1024:
1022:
1010:
1005:
1001:
997:
996:
990:
986:
982:
978:
974:
973:
967:
962:
957:
953:
949:
948:
942:
938:
934:
930:
926:
922:
918:
917:
912:
911:Tarjan, R. E.
907:
903:
899:
895:
891:
890:
884:
879:
874:
870:
866:
865:
859:
854:
849:
845:
841:
840:
834:
830:
826:
822:
818:
817:
812:
808:
803:
798:
794:
790:
789:
783:
778:
773:
768:
763:
759:
755:
750:
745:
740:
736:
732:
731:
725:
720:
716:
712:
708:
706:0-89871-432-X
702:
697:
696:
690:
686:
682:
678:
674:
670:
666:
662:
661:
656:
652:
648:
644:
640:
636:
635:
630:
626:
621:
616:
612:
608:
607:
602:
598:
594:
590:
586:
582:
581:
576:
572:
571:
567:
561:
560:Müller (1996)
556:
553:
550:
545:
542:
539:
534:
531:
528:
523:
520:
516:
512:
508:
503:
500:
496:
495:Farber (1983)
491:
488:
485:
480:
477:
474:
469:
466:
462:
457:
454:
450:
445:
442:
438:
434:
433:Farber (1983)
429:
426:
422:
418:
417:Farber (1983)
413:
410:
406:
402:
401:Farber (1983)
398:
393:
390:
386:
381:
378:
372:
370:
368:
364:
360:
352:
350:
348:
344:
328:
320:
312:
310:
308:
305:vertices and
304:
298:
294:
290:
286:
279:
277:
269:
267:
265:
260:
258:
253:
249:
247:
243:
239:
235:
231:
227:
223:
219:
215:
211:
207:
203:
197:
192:
186:
180:
174:
170:
165:
161:
156:
151:
147:
143:
139:
129:
122:
118:
111:
104:
100:
96:
92:
88:
84:
80:
78:
73:
65:
63:
61:
57:
53:
45:
41:
40:chordal graph
37:
30:
26:
22:
999:
993:
976:
970:
951:
945:
920:
914:
893:
887:
868:
862:
843:
837:
820:
814:
792:
786:
757:
753:
734:
728:
718:
715:
694:
664:
658:
638:
632:
610:
604:
584:
578:
555:
544:
533:
522:
507:Lubiw (1987)
502:
490:
479:
473:McKee (1999)
468:
456:
444:
428:
412:
397:Chang (1982)
392:
380:
367:split graphs
356:
316:
306:
302:
296:
292:
288:
284:
280:
273:
261:
254:
250:
245:
241:
237:
233:
229:
225:
221:
217:
213:
209:
205:
198:
190:
184:
178:
172:
168:
163:
159:
154:
149:
145:
141:
134:
127:
120:
116:
109:
102:
98:
94:
90:
82:
76:
69:
51:
35:
25:graph theory
21:mathematical
18:
909:Paige, R.;
777:11336/32705
327:leaf powers
270:Recognition
228:th and the
38:if it is a
1021:Categories
896:: 69–108,
568:References
313:Subclasses
115:,...} and
42:and every
811:Lubiw, A.
319:phylogeny
220:, if the
52:odd chord
937:33265037
60:distance
56:vertices
23:area of
681:6114466
309:edges.
244:th and
236:th and
126:,
108:,
50:has an
19:In the
935:
703:
679:
295:) log
283:O(min(
202:clique
933:S2CID
677:S2CID
373:Notes
167:. An
89:. An
44:cycle
27:, an
701:ISBN
361:and
153:and
79:-sun
1004:doi
1000:145
981:doi
956:doi
952:306
925:doi
898:doi
873:doi
869:156
848:doi
844:205
825:doi
797:doi
772:hdl
762:doi
739:doi
735:187
669:doi
643:doi
615:doi
611:310
589:doi
287:, (
140:in
34:is
1023::
998:,
977:45
975:,
950:,
931:,
921:16
919:,
894:42
892:,
867:,
842:,
821:16
819:,
793:43
791:,
770:,
758:34
756:,
733:,
675:,
663:,
639:98
637:,
609:,
585:11
583:,
513:;
509:;
435:;
419:;
403:;
399:;
369:.
299:))
291:+
259:.
1013:.
1006::
988:.
983::
965:.
958::
940:.
927::
905:.
900::
882:.
875::
857:.
850::
832:.
827::
806:.
799::
781:.
774::
764::
748:.
741::
723:.
717:K
710:.
684:.
671::
665:5
650:.
645::
624:.
617::
596:.
591::
517:.
497:.
451:.
339:k
335:k
331:k
325:-
323:k
307:m
303:n
297:n
293:m
289:n
285:n
246:l
242:j
238:k
234:j
230:l
226:k
222:i
218:l
214:k
210:j
206:i
194:2
191:w
188:2
185:u
182:1
179:w
176:1
173:u
169:n
164:n
160:i
158:(
155:u
150:i
146:u
142:W
137:i
135:w
131:2
128:w
124:1
121:w
117:W
113:2
110:u
106:1
103:u
99:U
95:n
91:n
83:n
81:(
77:n
48:G
32:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.