A matematika, azon belül a gráfelmélet területén egy fa -adik levélhatványa az a gráf, melynek csúcsai a levelei, élei pedig azokat a levélpárokat kötik össze, melyek -beli távolsága legfeljebb . Más megfogalmazásban a gráfhatvány egy feszített részgráfja, melyet levelei feszítenek ki. Egy ilyen módon konstruált gráf esetén az eredeti fát -adik levélgyökének nevezik. Egy gráf levélhatvány, ha egy gráf -levélhatványa valamely é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.; . 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 -levélhatványok korlátos -ra korlátos klikkszélességűek, de korlátlan kitevőre ez nem igaz.; .
Struktúra és felismerés
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 és 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
Jegyzetek
. . . . . . . . . . . . . . . . . .
Kategória:Gráfcsaládok Kategória:Perfekt gráfok