Phylogenetische Bäume k-Blattpotenzen von Bäumen (k-leaf powers) und Varianten
Final Report Abstract
Die mathematische Beschreibung von phylogenetischen Bäumen, d.h. von Bäumen, welche die Entwicklungsgeschichte von Taxa (z.B. biologischen Arten oder Sprachen) beschreiben, führt zu Graphen mit Baumstruktur und insbesondere zu speziellen chordalen Graphen: Nishimura, Ragde und Thilikos, motiviert durch den phylogenetischen Hintergrund, haben die Begriffe k-leaf power (k-Blattpotenz) und k-leaf root (k-Blattwurzel) wie folgt eingeführt: Ein endlicher ungerichteter Graph G = (V , E ) mit Knotenmenge V und Kantenmenge E heißt k-leaf power, wenn es einen Baum T gibt mit Blattmenge V (der Menge der Taxa), und Knoten x , y mit x <> y sind dann und nur dann adjazent (d.h. x y € E ) , wenn die Distanz von x und y in T höchstens k ist. Ein solcher Baum T heißt k-leaf root für G. Damit ist G induzierter Teilgraph der k-ten Potenz eines Baumes T, eingeschränkt auf die Blätter von T, und G ist dann bekanntlich sogar ein stark chordaler Graph. Durch neue Ergebnisse zu Potenzen von Bäumen und Blockgraphen sowie weitere Strukturergebnisse, die wir in unseren Arbeiten zum Projektthema erreicht haben, können wir wichtige Resultate u.a. von Nishimura, Ragde und Thilikos, von Rautenbach, von Dom, Guo, Hüffner und Niedermeler, von Kennedy, Lin und Yan, von Gurski und Wanke sowie von Fellows et al. verbessern. Als Beispiel sei folgendes Resultat genannt: Es war bekannt, daß jede k-leaf power auch (k + 2)-leaf power ist (dies sieht man leicht, indem man Blattkanten in einer entsprechenden leaf root durch neue Knoten unterteilt), jedoch war es ein offenes Problem, ob jede k-leaf power auch (k + 1)-leaf power ist. Kürzlich haben Fellows, Meister, Rosamond, Sritharan und Telle durch Angabe eines Beispiels gezeigt, daß nicht jede 4-leaf power auch 5-leaf power ist. Wir verallgemeinern dieses Resultat und zeigen, daß für alle k > 4 die Klassen der k-leaf powers und der (k + 1)-leaf powers unvergleichbar sind bzgl. Mengeninklusion. Darüber hinaus zeigen wir, daß für alle k > 6 und ungerade l mit 3 < l < k - 3, die Klassen der k-leaf powers und der (k + l)-leaf powers unvergleichbar sind bzgl. Mengeninklusion. Dies liefert ein voltständiges Schema aller Inklusionen bzw. Unvergleichbarkeiten zwischen solchen Klassen: Wir weisen nach, daß Inklusion zweier Klassen genau dann vorliegt, wenn sie auf triviale Welse durch Unterteilung von Kanten in einer entsprechenden k-leaf root erreichbar ist. Die Vereinigung der Klassen aller k-leaf powers ergibt die Klasse der leaf powers. Für diese Klasse ist weder eine strukturelle Charakterisierung bekannt noch ein effizienter Algorithmus zur Erkennung solcher Graphen. Wir haben nachgewiesen, daß leaf powers mit den (viel eher) von Bibelnieks und Dearing unter dem Namen fixed tolerance NeST graphs eingeführten und untersuchten Graphen übereinstimmen. Weiterhin Identifizieren wir als wichtige neue Teilklasse dieser Graphen die sogenannten rooted directed path graphs, welche die bekannten interval graphs verallgemeinern. Unsere Ergebnisse sind auf mehreren Internationalen Konferenzen, u.a. in Brasilien, Kanada, Israel und der tschechischen Republik jeweils ats Beiträge angenommen und vorgetragen worden.
Publications
- On (k, l)-leaf powers; Proceedings of MFCS 2007, L. Kucera and A. Kucera, eds., Lecture Notes in Comp. Sci. 4708, 525-535, 2007
A. Brandstädt, P. Wagner
- On k- versus (f + l)-leaf powers, Conference Proceedings COCOA 2008, Lecture Notes in Comp. Sci. 5165, 171- 179, 2008
A. Brandstädt, P. Wagner
- Ptolemaic graphs and interval graphs are leaf powers, Conference Proceedings LATIN 2008, E.S. Laber et al. (Eds.), Lecture Notes in Comp. Sci. 4957, 479-491, 2008
A. Brandstädt, C. Hundt
- Path-Bicolorable Graphs, Golumbic Festschrift, Lecture Notes in Comp. Sci. 5420 (2009) 172-182
A. Brandstädt, M.C. Golumbic, V.B. Le, M. Lipshteyn
- Simplicial powers of graphs. Conference Proceedings COCOA 2008, Lecture Notes in Comp. Sci. 5165, 160-170, 2008
A. Brandstädt, V.B. Le
