20:
172:
are strongly chordal and trees are strongly chordal, it follows that leaf powers are strongly chordal graphs. Actually, leaf powers form a proper subclass of strongly chordal graphs; a graph is a leaf power if and only if it is a fixed tolerance NeST graph and such graphs are a proper subclass of
234:, which also enable linear time recognition. Recognition of the 5-leaf and 6-leaf power graphs are also solved in linear time by Chang and Ko (2007) and Ducoffe (2018), respectively.
891:
114:
695:
563:
427:
996:
938:
812:
744:
650:
614:
586:
835:
50:
728:
915:
284:
276:
833:
Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width",
1091:
1086:
584:; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers",
65:
972:
780:
623:
169:
963:
57:
679:
645:
609:
581:
546:
Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers",
414:. Lecture Notes in Computer Science. Vol. 4769. Springer, Berlin, Heidelberg. pp. 109–120.
628:
977:
785:
43:
1064:
1046:
896:
798:
742:
Dahlhaus, E.; Manuel, P. D.; Miller, M. (1998), "A characterization of strongly chordal graphs",
667:
503:
477:
444:
185:
648:; Le, Van Bang; Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers",
691:
559:
495:
423:
1056:
1005:
982:
947:
924:
875:
844:
821:
790:
766:
753:
714:
659:
633:
595:
551:
534:
487:
415:
189:
81:
961:
Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees",
858:
573:
92:
854:
569:
257:
1017:
Raychaudhuri, A. (1992), "On powers of strongly chordal graphs and circular arc graphs",
1032:
889:
Lafond, Manuel (2021), "Recognizing k-leaf powers in polynomial time, for constant k",
684:
181:
952:
880:
757:
219:. Based on this characterization and similar ones, 3-leaf powers can be recognized in
1080:
1068:
825:
550:, Lecture Notes in Comput. Sci., vol. 4957, Springer, Berlin, pp. 479–491,
538:
507:
216:
443:
Ducoffe, Guillaume (2018-10-04). "Polynomial-time
Recognition of 4-Steiner Powers".
1037:
771:
671:
204:
32:
802:
612:; Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers",
555:
419:
220:
85:
28:
1060:
1009:
892:
Proceedings of the 2022 Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA)
600:
525:
Bibelnieks, E.; Dearing, P.M. (1993), "Neighborhood subtree tolerance graphs",
491:
910:
849:
794:
637:
499:
465:
663:
157:
986:
410:
Ko, Ming-Tat; Chang, Maw-Shang (2007-06-21). "The 3-Steiner Root
Problem".
936:
McKee, T. A. (1999), "A new characterization of strongly chordal graphs",
184:
and the larger class of rooted directed path graphs are leaf powers. The
19:
705:
Broin, M.W.; Lowe, T.J. (1986), "Neighborhood subtree tolerance graphs",
1033:"Parameterized Leaf Power Recognition via Embedding into Graph Products"
466:"Parameterized Leaf Power Recognition via Embedding into Graph Products"
215:
A graph is a 3-leaf power if and only if it is a (bull, dart, gem)-free
928:
718:
1051:
901:
810:
Farber, M. (1983), "Characterizations of strongly chordal graphs",
482:
449:
18:
866:
Hayward, R.B.; Kearney, P.E.; Malton, A. (2002), "NeST graphs",
207:, but this is not true of leaf powers with unbounded exponents.
726:
Dahlhaus, E.; Duchet, P. (1987), "On strongly chordal graphs",
690:, SIAM Monographs on Discrete Mathematics and Applications,
334:
177:
994:
Rautenbach, D. (2006), "Some remarks about leaf roots",
382:
23:
A tree (top) and its corresponding 3-leaf power (bottom)
188:
are exactly the leaf powers whose underlying trees are
302:
231:
95:
769:(2006), "Error compensation in leaf root problems",
338:
160:, the problem of reconstructing evolutionary trees.
268:makes this algorithm unsuitable for practical use.
683:
108:
354:
913:(1987), "Doubly lexical orderings of matrices",
264:. However, the high dependency on the parameter
226:Characterizations of 4-leaf powers are given by
366:
248:-leaf powers was unsolved for a long time, but
16:Graph representing leaves of a given tree graph
464:Eppstein, David; Havvaei, Elham (2020-08-01).
314:
64:and whose edges connect pairs of leaves whose
8:
412:Graph-Theoretic Concepts in Computer Science
397:
322:
370:
386:
271:Also, it has been proved that recognizing
227:
1050:
976:
951:
900:
879:
848:
784:
627:
599:
481:
448:
350:
100:
94:
682:; Le, Van Bang; Spinrad, Jeremy (1999),
295:
303:Nishimura, Ragde & Thilikos (2002)
249:
318:
232:Brandstädt, Le & Sritharan (2008)
7:
339:Hayward, Kearney & Malton (2002)
156:. These graphs have applications in
548:LATIN 2008: Theoretical informatics
199:-leaf powers for bounded values of
1031:Eppstein, D.; Havvaei, H. (2020),
256:-leaf powers can be recognized in
14:
707:SIAM J. Algebr. Discrete Methods
765:Dom, M.; Guo, J.; HĂĽffner, F.;
355:Bibelnieks & Dearing (1993)
651:ACM Transactions on Algorithms
615:Information Processing Letters
1:
953:10.1016/S0012-365X(99)00107-7
881:10.1016/s0166-218x(01)00207-4
758:10.1016/S0012-365X(97)00268-9
367:Brandstädt & Hundt (2008)
868:Discrete Applied Mathematics
836:Discrete Applied Mathematics
826:10.1016/0012-365X(83)90154-1
556:10.1007/978-3-540-78773-0_42
539:10.1016/0166-218X(93)90165-K
527:Discrete Applied Mathematics
420:10.1007/978-3-540-74839-7_11
315:Dahlhaus & Duchet (1987)
244:the recognition problem of
118:, induced by the leaves of
1108:
1061:10.1007/s00453-020-00720-8
1010:10.1016/j.disc.2006.03.030
601:10.1016/j.disc.2009.10.006
492:10.1007/s00453-020-00720-8
398:Brandstädt & Le (2006)
916:SIAM Journal on Computing
850:10.1016/j.dam.2008.08.031
795:10.1007/s00453-005-1180-z
638:10.1016/j.ipl.2006.01.004
371:Gurski & Wanke (2009)
277:fixed-parameter tractable
211:Structure and recognition
173:strongly chordal graphs.
164:Related classes of graphs
126:constructed in this way,
335:Brandstädt et al. (2010)
178:Brandstädt et al. (2010)
686:Graph Classes: A Survey
664:10.1145/1435375.1435386
351:Broin & Lowe (1986)
170:strongly chordal graphs
987:10.1006/jagm.2001.1195
279:when parameterized by
110:
24:
964:Journal of Algorithms
152:-leaf power for some
111:
109:{\displaystyle T^{k}}
22:
997:Discrete Mathematics
939:Discrete Mathematics
813:Discrete Mathematics
745:Discrete Mathematics
587:Discrete Mathematics
287:of the input graph.
93:
680:Brandstädt, Andreas
646:Brandstädt, Andreas
610:Brandstädt, Andreas
582:Brandstädt, Andreas
323:Raychaudhuri (1992)
186:indifference graphs
106:
60:are the leaves of
25:
1004:(13): 1456–1461,
697:978-0-89871-432-6
565:978-3-540-78772-3
387:Rautenbach (2006)
383:Dom et al. (2006)
228:Rautenbach (2006)
190:caterpillar trees
180:it is shown that
1099:
1071:
1054:
1045:(8): 2337–2359,
1026:
1019:Ars Combinatoria
1012:
989:
980:
956:
955:
946:(1–3): 245–247,
931:
905:
904:
884:
883:
874:(1–3): 139–153,
861:
852:
828:
820:(2–3): 173–189,
805:
788:
760:
752:(1–3): 269–271,
737:
729:Ars Combinatoria
721:
700:
689:
674:
640:
631:
604:
603:
576:
541:
512:
511:
485:
476:(8): 2337–2359.
461:
455:
454:
452:
440:
434:
433:
407:
401:
395:
389:
380:
374:
364:
358:
348:
342:
332:
326:
312:
306:
300:
282:
275:-leaf powers is
274:
267:
263:
255:
247:
243:
202:
198:
168:Since powers of
155:
151:
140:
134:
129:
125:
121:
117:
115:
113:
112:
107:
105:
104:
82:induced subgraph
79:
75:
71:
63:
55:
48:
39:
1107:
1106:
1102:
1101:
1100:
1098:
1097:
1096:
1077:
1076:
1075:
1030:
1016:
993:
960:
935:
929:10.1137/0216057
909:
888:
865:
832:
809:
767:Niedermeier, R.
764:
741:
725:
719:10.1137/0607039
704:
698:
678:
644:
629:10.1.1.144.3486
608:
580:
566:
545:
524:
520:
515:
463:
462:
458:
442:
441:
437:
430:
409:
408:
404:
396:
392:
381:
377:
365:
361:
349:
345:
333:
329:
313:
309:
301:
297:
293:
280:
272:
265:
261:
258:polynomial time
253:
245:
238:
213:
200:
196:
182:interval graphs
166:
153:
149:
138:
132:
127:
123:
119:
96:
91:
90:
88:
77:
73:
69:
61:
53:
46:
37:
17:
12:
11:
5:
1105:
1103:
1095:
1094:
1092:Perfect graphs
1089:
1087:Graph families
1079:
1078:
1074:
1073:
1028:
1014:
991:
978:10.1.1.43.1127
958:
933:
923:(5): 854–879,
907:
886:
863:
843:(4): 583–595,
830:
807:
786:10.1.1.218.490
779:(4): 363–381,
762:
739:
723:
702:
696:
676:
642:
622:(4): 133–138,
606:
594:(4): 897–910,
578:
564:
543:
521:
519:
516:
514:
513:
456:
435:
428:
402:
390:
375:
359:
343:
327:
307:
294:
292:
289:
260:for any fixed
212:
209:
165:
162:
122:. For a graph
103:
99:
15:
13:
10:
9:
6:
4:
3:
2:
1104:
1093:
1090:
1088:
1085:
1084:
1082:
1070:
1066:
1062:
1058:
1053:
1048:
1044:
1040:
1039:
1034:
1029:
1024:
1020:
1015:
1011:
1007:
1003:
999:
998:
992:
988:
984:
979:
974:
970:
966:
965:
959:
954:
949:
945:
941:
940:
934:
930:
926:
922:
918:
917:
912:
908:
903:
898:
895:: 1384–1410,
894:
893:
887:
882:
877:
873:
869:
864:
860:
856:
851:
846:
842:
838:
837:
831:
827:
823:
819:
815:
814:
808:
804:
800:
796:
792:
787:
782:
778:
774:
773:
768:
763:
759:
755:
751:
747:
746:
740:
735:
731:
730:
724:
720:
716:
712:
708:
703:
699:
693:
688:
687:
681:
677:
673:
669:
665:
661:
657:
653:
652:
647:
643:
639:
635:
630:
625:
621:
617:
616:
611:
607:
602:
597:
593:
589:
588:
583:
579:
575:
571:
567:
561:
557:
553:
549:
544:
540:
536:
532:
528:
523:
522:
517:
509:
505:
501:
497:
493:
489:
484:
479:
475:
471:
467:
460:
457:
451:
446:
439:
436:
431:
429:9783540748380
425:
421:
417:
413:
406:
403:
399:
394:
391:
388:
384:
379:
376:
372:
368:
363:
360:
356:
352:
347:
344:
340:
336:
331:
328:
324:
320:
316:
311:
308:
304:
299:
296:
290:
288:
286:
278:
269:
259:
251:
250:Lafond (2021)
241:
235:
233:
229:
224:
222:
218:
217:chordal graph
210:
208:
206:
203:have bounded
193:
191:
187:
183:
179:
174:
171:
163:
161:
159:
147:
144:A graph is a
142:
136:
101:
97:
87:
83:
67:
59:
52:
45:
41:
34:
30:
21:
1042:
1038:Algorithmica
1036:
1022:
1018:
1001:
995:
968:
962:
943:
937:
920:
914:
890:
871:
867:
840:
834:
817:
811:
776:
772:Algorithmica
770:
749:
743:
733:
727:
710:
706:
685:
655:
649:
619:
613:
591:
585:
547:
530:
526:
473:
470:Algorithmica
469:
459:
438:
411:
405:
393:
378:
362:
346:
330:
319:Lubiw (1987)
310:
298:
270:
252:showed that
239:
236:
225:
214:
205:clique-width
194:
175:
167:
145:
143:
131:
130:is called a
36:
33:graph theory
29:mathematical
26:
713:: 348–357,
221:linear time
148:if it is a
86:graph power
76:. That is,
72:is at most
40:-leaf power
1081:Categories
1052:1810.02452
971:: 69–108,
902:2110.15421
518:References
483:1810.02452
450:1810.02304
285:degeneracy
146:leaf power
135:-leaf root
1069:218988055
1025:: 147–160
973:CiteSeerX
911:Lubiw, A.
781:CiteSeerX
624:CiteSeerX
533:: 13–26,
508:218988055
500:1432-0541
158:phylogeny
658:: 1–22,
283:and the
66:distance
58:vertices
31:area of
859:2499471
736:: 23–30
672:6114466
574:2472761
116:
89:
84:of the
27:In the
1067:
975:
857:
801:
783:
694:
670:
626:
572:
562:
506:
498:
426:
80:is an
56:whose
1065:S2CID
1047:arXiv
897:arXiv
803:75279
799:S2CID
668:S2CID
504:S2CID
478:arXiv
445:arXiv
291:Notes
51:graph
49:is a
42:of a
734:24 B
692:ISBN
560:ISBN
496:ISSN
424:ISBN
237:For
230:and
195:The
44:tree
35:, a
1057:doi
1006:doi
1002:306
983:doi
948:doi
944:205
925:doi
876:doi
872:121
845:doi
841:157
822:doi
791:doi
754:doi
750:187
715:doi
660:doi
634:doi
596:doi
592:310
552:doi
535:doi
488:doi
416:doi
242:≥ 7
176:In
137:of
68:in
1083::
1063:,
1055:,
1043:82
1041:,
1035:,
1023:34
1021:,
1000:,
981:,
969:42
967:,
942:,
921:16
919:,
870:,
855:MR
853:,
839:,
818:43
816:,
797:,
789:,
777:44
775:,
748:,
732:,
709:,
666:,
654:,
632:,
620:98
618:,
590:,
570:MR
568:,
558:,
531:43
529:,
502:.
494:.
486:.
474:82
472:.
468:.
422:.
385:;
369:;
353:;
337:;
321:;
317:;
223:.
192:.
141:.
1072:.
1059::
1049::
1027:.
1013:.
1008::
990:.
985::
957:.
950::
932:.
927::
906:.
899::
885:.
878::
862:.
847::
829:.
824::
806:.
793::
761:.
756::
738:.
722:.
717::
711:7
701:.
675:.
662::
656:5
641:.
636::
605:.
598::
577:.
554::
542:.
537::
510:.
490::
480::
453:.
447::
432:.
418::
400:.
373:.
357:.
341:.
325:.
305:.
281:k
273:k
266:k
262:k
254:k
246:k
240:k
201:k
197:k
154:k
150:k
139:G
133:k
128:T
124:G
120:T
102:k
98:T
78:G
74:k
70:T
62:T
54:G
47:T
38:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
