Levélhatvány

Egy fa (felül) és a hozzá tartozó 3-levélhatványa (alul)

A matematika, azon belül a gráfelmélet területén egy $T$ fa k-adik levélhatványa az a $G$ gráf, melynek csúcsai a $T$ levelei, élei pedig azokat a levélpárokat kötik össze, melyek $T$-beli távolsága legfeljebb $k$. Más megfogalmazásban $G$ a $T^{k}$ gráfhatvány egy feszített részgráfja, melyet $T$ levelei feszítenek ki. Egy ilyen módon konstruált $G$ gráf esetén az eredeti $T$ fát $G$ k-adik levélgyökének nevezik. Egy gráf levélhatvány, ha egy gráf $k$-levélhatványa valamely $k$ értékre. Az ilyen gráfoknak a filogenetikus (leszármazási alapú) rendszertan evolúciós fáinak rekonstrukciójában van szerepe.

Kapcsolódó gráfcsaládok

Mivel az erősen merev körű gráfok hatványai is erősen merev körűek, valamint a fák is erősen merev körűek, ezért a levélhatványok mindig erősen merev körű gráfok. Valójában a levélhatványok az erősen merev körű gráfok valódi részhalmazai; egy gráf pontosan akkor levélhatvány, ha egy fixed tolerance NeST gráf (neighborhood subtree tolerance gráf), melyek viszont az erősen merev körű gráfok valódi részhalmazai. (Brandstädt et al. 2010) megmutatják, hogy az intervallumgráfok, valamint a gyökeres irányított útgráfok nagyobb osztálya is levélhatvány. Az egység-intervallumgráfok pontosan azok a levélhatványok, melyek alapjait hernyófák képezik. A k-levélhatványok korlátos k-ra korlátos klikkszélességűek, de korlátlan kitevőre ez nem igaz.

Struktúra és felismerés

A számítástudomány megoldatlan problémája: Létezik-e polinom idejű algoritmus a levélhatványok, illetve $k\geq 5$ $k$-levélhatványok felismerésére? (A számítástudomány további megoldatlan problémái)

Egy gráf akkor és csak akkor 2-levélhatvány, ha előáll klikkek diszjunkt uniójaként (tehát klasztergráf). Egy gráf pontosan akkor 3-levélhatvány, ha egy (bull,dart,gem)-mentes merev körű gráf. Ilyen és hasonló karakterizációk alapján a 3-levélhatványok lineáris időben felismerhetők. A 4-levélhatványok karakterizációját (Rautenbach 2006) és (Brandstädt, Le & Sritharan 2008) adják meg, ez szintén lehetővé teszi a lineáris idejű felismerést. A k ≥ 5 hatványokra a k-levélhatványok felismerése még nyitott kérdés, így az is, hogy általában a levélhatványok polinom időben felismerhetők-e.

Fordítás

• Ez a szócikk részben vagy egészben a Leaf power című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Bibelnieks, E. & Dearing, P.M. (1993), "Neighborhood subtree tolerance graphs", Discrete Applied Mathematics 43: 13–26, DOI 10.1016/0166-218X(93)90165-K.
• Brandstädt, Andreas & Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers", LATIN 2008: Theoretical informatics, vol. 4957, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 479–491, DOI 10.1007/978-3-540-78773-0_42.
• Brandstädt, Andreas; Hundt, Christian & Mancini, Federico et al. (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics 310: 897–910, DOI 10.1016/j.disc.2009.10.006.
• Brandstädt, Andreas & Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers", Information Processing Letters 98: 133–138, DOI 10.1016/j.ipl.2006.01.004.
• Brandstädt, Andreas; Le, Van Bang & Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers", ACM Transactions on Algorithms 5: Article 11.
• Brandstädt, Andreas; Le, Van Bang & Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Broin, M.W. & Lowe, T.J. (1986), "Neighborhood subtree tolerance graphs", SIAM J. Algebraic and Discrete Meth. 7: 348–357.
• Dahlhaus, E. & Duchet, P. (1987), "On strongly chordal graphs", Ars Combinatoria 24 B: 23–30.
• Dahlhaus, E.; Manuel, P. D. & Miller, M. (1998), "A characterization of strongly chordal graphs", Discrete Mathematics 187 (1–3): 269–271, DOI 10.1016/S0012-365X(97)00268-9.
• Dom, M.; Guo, J. & Hüffner, F. et al. (2006), "Error compensation in leaf root problems", Algorithmica 44: 363–381, DOI 10.1007/s00453-005-1180-z.
• Farber, M. (1983), "Characterizations of strongly chordal graphs", Discrete Mathematics 43 (2–3): 173–189, DOI 10.1016/0012-365X(83)90154-1.
• Gurski, Frank & Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width", Discrete Applied Mathematics 157 (4): 583–595, DOI 10.1016/j.dam.2008.08.031.
• Hayward, R.B.; Kearney, P.E. & Malton, A. (2002), "NeST graphs", Discrete Applied Mathematics 121: 139–153, DOI 10.1016/s0166-218x(01)00207-4.
• Lubiw, A. (1987), "Doubly lexical orderings of matrices", SIAM Journal on Computing 16 (5): 854–879, DOI 10.1137/0216057.
• McKee, T. A. (1999), "A new characterization of strongly chordal graphs", Discrete Mathematics 205 (1–3): 245–247, DOI 10.1016/S0012-365X(99)00107-7.
• Nishimura, N.; Ragde, P. & Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms 42: 69–108, DOI 10.1006/jagm.2001.1195.
• Rautenbach, D. (2006), "Some remarks about leaf roots", Discrete Mathematics 306: 1456–1461, DOI 10.1016/j.disc.2006.03.030.
• Raychaudhuri, A. (1992), "On powers of strongly chordal graphs and circular arc graphs", Ars Combinatoria 34: 147–160.