Listová síla - Leaf power

Strom (nahoře) a jeho odpovídající síla 3 listů (dole)

V matematický oblast teorie grafů, a k- listová síla stromu ${ displaystyle T}$ je graf ${ displaystyle G}$ jehož vrcholy jsou listy ${ displaystyle T}$ a jejichž okraje spojují páry listů, jejichž vzdálenost je v ${ displaystyle T}$ je nanejvýš ${ displaystyle k}$. To znamená, ${ displaystyle G}$ je indukovaný podgraf z výkon grafu ${ displaystyle T ^ {k}}$, vyvolané listy ${ displaystyle T}$. Pro graf ${ displaystyle G}$ takto postavené, ${ displaystyle T}$ se nazývá a k- kořen listu z ${ displaystyle G}$.

Graf je a listová síla pokud je to ${ displaystyle k}$- listová síla pro některé ${ displaystyle k}$.^[1] Tyto grafy mají aplikace v fylogeneze, problém rekonstrukce evolučních stromů.

Související třídy grafů

Vzhledem k tomu, pravomoci silně chordální grafy jsou silně chordální a stromy jsou silně chordální, z toho vyplývá, že listové síly jsou silně chordální grafy.^[2] Ve skutečnosti listové síly tvoří vlastní podtřídu silně chordálních grafů; graf je síla listu právě tehdy, pokud jde o NeST graf s pevnou tolerancí^[3] a takové grafy jsou vhodnou podtřídou silně chordálních grafů.^[4]

v Brandstädt a kol. (2010) je ukázáno, že intervalové grafy a větší třída zakořeněných směrovaných grafů cesty jsou listové síly. The indiferenční grafy jsou přesně listové síly, jejichž podkladové stromy jsou housenky.

The k- listové síly pro omezené hodnoty k ohraničené šířka kliky, ale to neplatí pro listové síly s neomezenými exponenty.^[5]

Struktura a uznání

Nevyřešený problém v informatice: Existuje algoritmus polynomiálního času pro rozpoznávání pravomocí listu nebo ${ displaystyle k}$- listové pravomoci pro ${ displaystyle k geq 7}$? (více nevyřešených problémů v informatice)

Graf je 2křídlá síla právě tehdy, je-li to disjunktní unie z kliky (tj. a shlukový graf ).^[1]

Graf je síla 3 listů, právě když je zdarma (býk, šipka, drahokam) chordální graf.^[6]Na základě této a podobných charakteristik lze v 3 rozpoznat moc 3 listů lineární čas.^[7]

Charakterizace 4křídlých sil jsou dány Rautenbach (2006) a Brandstädt, Le & Sritharan (2008), které také umožňují lineární rozpoznávání času. Rozpoznání výkonových grafů s 5 a 6 křídly řeší v lineárním čase také Chang a Ko (2007)^[8] a Ducoffe (2018),^[9] resp.

Pro ${ displaystyle k}$ ≥ 7 problém s rozpoznáním ${ displaystyle k}$-listové pravomoci jsou otevřené a stejně tak je otevřeným problémem, zda v nich lze rozpoznat listové pravomoci polynomiální čas. Bylo však prokázáno, že uznání ${ displaystyle k}$- listová moc je fixovatelný parametr při parametrizaci pomocí ${ displaystyle k}$ a zvrhlost vstupního grafu.^[10]

Poznámky

Reference