ネットワークの耐故障性を考慮したグラフ構造的性質に関する研究

考虑网络容错的图结构特性研究

基本信息

批准号：
19K11829
负责人：
蓮沼徹
金额：
$ 1.66万
依托单位：
The University of Tokushima
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2019
资助国家：
日本
起止时间：
2019-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

Mader予想とは，位数mの任意の木Tに対して，最小次数が[3k/2]+m-1以上の全てのk-連結グラフGは，G-V(T')がk-連結であるTに同型な部分木T'を含む，という命題である．この予想について，Tがパスのとき，k = 1のときは成立し，k = 2のときは部分的な肯定的結果が知られていたが，最近 k = 2,3の場合も成り立つことが示されている．本研究では，Mader予想の辺版として，次の命題を予想し，k <= 2のときには成り立つことを証明した．予想１：位数mの任意の木Tに対して，最小次数がk+m-1以上の全てのk-連結グラフ（k-辺連結グラフ）Gは，G-E(T')がk-連結（k-辺連結）であるTに同型な部分木T'を含む.実際にはより強い以下の命題を証明した．命題１：k <= 2として，位数mの任意の木Tに対して，最小次数がmax{Δ(T)+k,m-1}以上の全てのk-連結グラフ（k-辺連結グラフ）Gは，G-E(T')がk-連結（k-辺連結）であるTに同型な部分木T'を含む,ここでΔ(T)はTの最大次数を表す．また，予想１に関して，最小次数の下界を2(k+m-p)，ただしp = [(k(k+1)+(m-1)(m-4))/2n+1/2]+2，と緩和した場合には成り立つことも示した．さらに，Erdos-Sos予想とLoebl-Komlos-Sos予想の両方が正しければ，k-連結グラフに対する予想１が成り立つことも証明した．特に，この結果とこれまでに知られているErdos-Sos予想とLoebl-Komlos-Sos予想の肯定的結果から，k-連結グラフに対する予想1はTをパスに限定した場合及びGを内周が7以上と限定した場合に成立することが分かった．また，Loebl-Komlos-Sos予想が正しい場合は密なグラフでは予想１が成り立つことも証明した．

MADER预测是一个命题，即对于M的任何树T，所有K相互连接的图G均具有[3K/2]+M-1或更高的最小级数，包括子树T'，其中t'与t同构为t，其中G-V（t'）均为k连接。关于这一预测，当t是通过时，k = 1是正确的，当k = 2是一个积极的结果时，最近表明它对于k = 2和3也是如此。在这项研究中，我们将以下命题预测为Mader预测的边缘版本，并证明当k <= 2时，它在k <= 2的范围内表明，所有的链接是k-c的图形。 K+M-1或更高的子树包括与t的同构t'，其中g-e（t'）是k连接的（k侧链接）。实际上，我们证明了以下命题更强。命题1：假设k <= 2，对于m的任何树t，所有k连接的图（k侧链接图）g具有最小级数为最大序列，或更多级别{δ（t）+k，m-1}或更多，或更多的子树t'包括对t的子树t'，t'与t相同，其中g-e（t'）均在k-connection（k-connect）（k-content）（k-content）（k-content），the the the the the the the the the（t）（t）（T）（t）（t）（t）。 1，如果在2（k+m-p）下放松最小顺序的下限，但是p = [（k（k+1）+（m-1）（m-4）（m-4））/2n+1/2] +2。此外，还证明，如果ERDOS-SOS预测和LOEBL-KOMLOS-SOS预测都是正确的，那么对于K concateNation的图1均为true。特别是，从这个结果以及先前已知的ERDOS-SOS和LOEBL-KOMLOS-SOS预测的阳性结果，可以发现，当t限于Pass和G限于7或更多的内周长时，对于K concotatenate的图1是有效的。它还证明，如果Loebl-Komlos-SOS预测正确，则预测1在密集图上有效。