Levélhatvány

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.^[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

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).^[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

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.

Matematikaportál • összefoglaló, színes tartalomajánló lap

[FOOTNOTENishimuraRagdeThilikos2002-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)

[FOOTNOTEBrandstädtLe2006-7] Brandstädt & Le (2006).

[1]

[2]

[3]

[4]

[5]

[6]

[7]