葉功率

在圖理論的數學領域中,樹t的k層功率是圖G ,其頂點是t的葉子,其邊緣的邊緣連接了一對葉子的葉子,其在t中的距離最多為k 。也就是說, G是圖形功率的誘導子圖 ,由t的葉子誘導。對於以這種方式構造的圖G , T稱為G的K-葉根。
如果某些k是k-葉功率,則圖是葉子的功率。這些圖具有系統發育,這是重建進化樹的問題。
圖形的相關類
由於強烈的和弦圖的力量是強烈的弦,樹木是強烈的弦,因此葉子的力量是強烈的和弦圖。實際上,葉子能力構成了強烈的弦圖的適當子類。當且僅當它是固定的公差巢圖時,圖形是葉子的功率,並且此類圖是強烈的弦圖的適當子類。
在Brandstädt等人中。 (2010年)表明,間隔圖和較大的根係有向路徑圖是葉子功率。冷漠的圖形正是葉子的底層樹是毛毛蟲樹。
k的有界值的k葉冪具有有界的集合寬度,但對於帶有無限指數的葉子力量並非如此。
結構和認可
當且僅當它是(公牛,飛鏢,寶石) - 無弦圖時,圖是3葉的功率。基於此特徵和類似的特徵,可以在線性時間內識別3葉功能。
Rautenbach(2006)和Brandstädt,Le&Sritharan(2008)給出了4葉能力的特徵,這也啟用了線性時間識別。 Chang和Ko(2007)和Ducoffe(2018)分別在線性時間求解了5葉和6葉功率圖的識別。
對於K≥7 ,長期無法解決K-葉功率的識別問題,但Lafond(2021)表明,對於任何固定的K ,可以在多項式時間內識別K-葉冪。但是,對參數k的高依賴性使得該算法不適合實際使用。