关于直径为2-临界图的Murty-Simon猜想

称图G是直径为2-临界图,如果G的直径是2,任意删掉一条边这个图的直径都会增加。一个非常著名的猜想,称为Murty-Simon猜想,指出对于任意有n个点的直径为2-临界图,它的边数最多为[n^(2)/4],且为完全二部图K_([n/2],[n/2])时可以取到边数的上界。一个图称为是3_(t)-临界图,简记为3_(t)EC,如果它的全控制数是3,并且任意加一条边全控制数都会减少。利用直径为2-临界图和全控制边临界图之间的关系,要证明Murty-Simon猜想只需要证明n个点的3_(t)EC图,它的边数大于[n(n-2)/4]。设δ(G)和α(G)分别表示G的最小度和独立数。最后,得到了3_(t)EC图G一定满足α(G)≤δ(G)+2。并且,对于满足α(G)=δ(G)+2的3_(t)EC图G,猜想一定是成立的。