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 ${\displaystyle T}$ fa k-adik levélhatványa az a ${\displaystyle G}$ gráf, melynek csúcsai a ${\displaystyle T}$ levelei, élei pedig azokat a levélpárokat kötik össze, melyek ${\displaystyle T}$-beli távolsága legfeljebb ${\displaystyle k}$. Más megfogalmazásban ${\displaystyle G}$ a ${\displaystyle T^{k}}$ gráfhatvány egy feszített részgráfja, melyet ${\displaystyle T}$ levelei feszítenek ki. Egy ilyen módon konstruált ${\displaystyle G}$ gráf esetén az eredeti ${\displaystyle T}$ fát ${\displaystyle G}$ k-adik levélgyökének nevezik. Egy gráf levélhatvány, ha egy gráf ${\displaystyle k}$-levélhatványa valamely ${\displaystyle k}$ értékre.[1] 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.[2] 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),[3] melyek viszont az erősen merev körű gráfok valódi részhalmazai.[4] (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.[5]

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 ${\displaystyle k\geq 5}$ ${\displaystyle 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).[1] Egy gráf pontosan akkor 3-levélhatvány, ha egy (bull,dart,gem)-mentes merev körű gráf.[6] Ilyen és hasonló karakterizációk alapján a 3-levélhatványok lineáris időben felismerhetők.[7] 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

1. Nishimura, Ragde & Thilikos (2002).
2. (Dahlhaus & Duchet 1987); (Lubiw 1987); (Raychaudhuri 1992).
3. (Brandstädt et al. 2010); (Hayward, Kearney & Malton 2002).
4. (Broin & Lowe 1986); (Bibelnieks & Dearing 2006).
5. (Brandstädt & Hundt 2008); (Gurski & Wanke 2009).
6. (Dom et al. 2006); (Rautenbach 2006)
7. Brandstädt & Le (2006).

• 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.