線形樹木性

数学の一分野であるグラフ理論において、無向グラフの線状樹木度とは、その辺を分割できる線状フォレストの最小数です。ここで、線状フォレストとは、最大次数が 2 の非巡回グラフです。つまり、パス グラフの互いに素な和集合です。線状樹木度は、辺を分割できるフォレストの最小数である樹木度の変形です。

最大次数のグラフの線形樹状性は少なくとも であることが知られており、最大 であると推測されます。この推測は、奇数次数のグラフの場合、両方の式が等しいため、線形樹状性を正確に決定します。偶数次数のグラフの場合、線形樹状性は 2 つの可能な値のうちの 1 つでなければならないことを意味しますが、これら 2 つの選択肢の正確な値を決定することはNP 完全です。 ${\displaystyle \Delta }$${\displaystyle \lceil \Delta /2\rceil }$${\displaystyle \lceil (\Delta +1)/2\rceil }$

数学における未解決の問題:

最大次数のグラフはすべて、最大で線形樹状性を持ちますか?${\displaystyle \Delta }$${\displaystyle \lceil (\Delta +1)/2\rceil }$

（数学における未解決の問題がさらに増える）

最大次数を持つグラフの線型樹木性は、常に少なくとも です。これは、各線型フォレストが最大次数頂点の辺を 2 つしか使用できないためです。Akiyama 、Exoo、Harary (1981) の線型樹木性予想は、この下限も厳密であるというものです。彼らの予想によると、すべてのグラフの線型樹木性は最大でも です。^[1]ただし、これは のまま証明されておらず、線型樹木性の最も証明された上限は、 Ferber、Fox、Jain による定数に対していくらか大きくなります 。 ^[2]${\displaystyle G}$${\displaystyle \Delta }$${\displaystyle \lceil \Delta /2\rceil }$${\displaystyle \lceil (\Delta +1)/2\rceil }$${\displaystyle \Delta /2+O(\Delta ^{2/3-c})}$${\displaystyle c>0}$

グラフの線型樹木性が に等しくなるためには、が偶数で、各線型フォレストには次数 の各頂点に接続する 2 つの辺がなければなりません。しかし、パスの終点にある頂点では、そのパスを含むフォレストには接続辺が 1 つしかないため、その頂点の次数は に等しくなりません。したがって、線型樹木性が に等しいグラフには、次数が最大値未満の頂点がいくつかなければなりません。正則グラフにはそのような頂点はなく、線型樹木性が に等しくなることはありません。したがって、正則グラフでは、線型樹木性予想から、線型樹木性がちょうど であることが示唆されます。 ${\displaystyle \Delta /2}$${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta /2}$${\displaystyle \Delta /2}$${\displaystyle \lceil (\Delta +1)/2\rceil }$

線形樹木性は、グラフのエッジを分割できる最小のフォレスト数である樹木性のバリエーションです。研究者は、線形樹木性のバリエーションである線形k樹木性も研究しており、線形フォレスト内の各パスは最大でk個のエッジを持つことができます。^[3]

関連するもう 1 つの問題は、ハミルトン分解です。これは、偶数次の正則グラフを正確にハミルトン閉路に分解する問題です。グラフから任意の頂点を 1 つ削除して形成される部分グラフが線形樹状性を持つ場合のみ、グラフにハミルトン分解が存在します。 ${\displaystyle \Delta }$${\displaystyle \Delta /2}$ ${\displaystyle \Delta /2}$

多項式時間で決定できる樹木性とは異なり、線形樹木性はNP困難です。線形樹木性が2であるグラフを認識することさえNP完全です。^[4]しかし、立方体グラフや最大次数が3のその他のグラフの場合、線形樹木性は常に2であり、^[1]深さ優先探索に基づくアルゴリズムを使用して、2つの線形フォレストへの分解を線形時間で見つけることができます。^[5]