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

On Murty-Simon Conjecture of Diameter 2-Critical Graphs

作　　者：徐文琴 Xu Wenqin(North China University of Technology,Beijing 100144,China)

机构地区：[1]北方工业大学,北京100144

出　　处：《廊坊师范学院学报（自然科学版）》2021年第2期5-9,共5页Journal of Langfang Normal University(Natural Science Edition)

基　　金：国家自然基金青年项目(11701010);北京市教委项目(KM202010009012);北方工业大学青年毓优人才项目(207051360020XN140/008)。

摘　　要：称图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,猜想一定是成立的。A graph is diameter 2-critical if its diameter is two and the deletion of any edge increases the diameter.A wellstudied conjecture,known as the Murty and Simon conjecture states that the number of edges in a diameter 2-critical graph of order n is at most[n^(2)/4]and that the extremal graphs are the complete bipartite graphs K_([n/2],[n/2]).A graph is 3_(t)-critical,abbreviated 3_(t)EC,if its total domination number is 3 and the addition of any edge decreases the total domination number.By using the relationship between diameter 2-critical graphs with the total domination edge critical graphs,it is known that proving Murty-Simon conjecture is equivalent to proving that the number of edges in a 3_(t)EC graph of order n is greater than[n(n-2)/4].Letδ(G)andα(G)be the minimum degree and the independent number of a graph G,respectively.In this paper,we show that for a 3_(t)EC graph G,it satisfiesα(G)≤δ(G)+2.Finally,we prove the conjecture for 3_(t)EC graphs G who have the maximum independent number,that isα(G)=δ(G)+2.

关 键 词：直径为2-临界图 全控制边临界图 γ_(t)-临界图 

分 类 号：O157.5[理学—数学]