關(guān)于直徑為2-臨界圖的Murty-Simon猜想

徐文琴

【摘? ?要】? ?稱圖[G]是直徑為2-臨界圖，如果[G]的直徑是2，任意刪掉一條邊這個圖的直徑都會增加。一個非常著名的猜想，稱為Murty-Simon猜想，指出對于任意有[n]個點的直徑為2-臨界圖，它的邊數(shù)最多為[n24]，且為完全二部圖[Kn2，n2]時可以取到邊數(shù)的上界。一個圖稱為是[3t]-臨界圖，簡記為[3tEC]，如果它的全控制數(shù)是3，并且任意加一條邊全控制數(shù)都會減少。利用直徑為2-臨界圖和全控制邊臨界圖之間的關(guān)系，要證明Murty-Simon猜想只需要證明[n]個點的[3tEC]圖，它的邊數(shù)大于[n（n-2）/4]。設(shè)[δ（G）]和[α（G）]分別表示[G]的最小度和獨立數(shù)。最后，得到了[3tEC]圖[G]一定滿足[α（G）≤δ（G）+2]。并且，對于滿足[α（G）=δ（G）+2]的[3tEC]圖[G]，猜想一定是成立的。

【關(guān)鍵詞】? ?直徑為2-臨界圖;全控制邊臨界圖;[γt]-臨界圖

On Murty-Simon Conjecture of Diameter 2-Critical Graphs

Xu Wenqin

（North China University of Technology， Beijing 100144， China）

【Abstract】? ? A graph is diameter 2-critical if its diameter is two and the deletion of any edge increases the diameter. A well-studied 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[n24]and that the extremal graphs are the complete bipartite graphs [Kn2，n2].A graph is[3t]-critical， abbreviated[3tEC]， 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[3tEC]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[3tEC]graph [G]， it satisfies[α（G）≤δ（G）+2]. Finally， we prove the conjecture for[3tEC]graphs [G] who have the maximum independent number， that is [α（G）=δ（G）+2].

【Key words】? ? ?diameter 2-critical graph; total domination edge critical graph; [γt]-critical graph

〔中圖分類號〕? O157.5 ? ?〔文獻標識碼〕? A ? ? ? ? ? ? ?〔文章編號〕 1674 - 3229（2021）02- 0005 - 05

0? ? ?基本概念

關(guān)于圖論中的符號和術(shù)語建議讀者參考文獻[1]。設(shè)[G=（V（G），E（G））]是一個圖，其中頂點集為[V（G）]，邊集為[E（G）]。設(shè)[v∈V（G）]，點[v]的開鄰域指的是集合[N（v）={u∈V|uv∈E（G）}]，而點[v]的閉鄰域指的是集合[N[v]=N（v）?{v}]。對于任意的[v∈V（X）]，用[N（v）]來表示點[v]在[X]中的鄰域。對于子集[S?V（G）]，它的開鄰域指的是集合[N（S）=v∈SN（v）]，而閉鄰域指的是集合[N[S]=N（S）?S]。圖[G]的補圖[G]的頂點集合為[V（G）]，而邊集合為[{xy|{x，y}?V（G），xy?E（G）}]。用[G[S]]來表示由非空子集[S?V（G）]所誘導(dǎo)的子圖，且設(shè)[G-S=G[V（G）-S]]。用[deg（v，S）]來表示子集[S?V（G）]中與[v] 相連的點數(shù)，特別地，如果[S=V（G）]，則把它簡記為[deg（v）]。符號[α（G）]和[δ（G）]分別表示圖[G]的獨立數(shù)和最小度。通常還把[α（G）]和[δ（G）]分別簡記為[α]和[δ]。圖[G]的所有點對的最長距離稱為圖[G]的直徑，記為[diam（G）]。用[S]來表示集合[S]的基數(shù)。

控制集理論由于其廣泛的應(yīng)用和理論意義，故而成為圖論中非常重要的一部分，見文獻 [2，3]。如果對于任意的[v∈V（G）]，有[v∈S]或者[v]與[S]中的某個點相連，也即[N[S]=V（G）]，則子集[S?V（G）]稱為是[G]的控制集，記為[DS]。圖[G]的控制數(shù)指的是[G]的所有控制集的最小基數(shù)，記為[γ（G）]?？刂七吪R界圖的概念則是由Sumner和Blitch在文獻[4]中引進的。稱圖[G]是控制邊臨界的，或者[γEC]，如果對于任意一條邊[e∈E（G）]，有[γ（G+e）<γ（G）]。若圖[G]是[γEC]且[γ（G）=k]，則稱[G]是 [k]-臨界的。設(shè)[G]是一個沒有孤立點的圖，若[S]是[G]的一個子集滿足[G]的每一個點都與[S]中的某一個點相連，也即[N（S）=V（G）]，則稱[S]是[G]的一個全控制集，記為[TDS]。注意到每一個沒有孤立點的圖都至少有一個[TDS]，因為[S=V（G）]就是一個全控制集。圖[G]的所有[TDS]的最小基數(shù)就稱作為全控制數(shù)，記為[γt（G）]。圖[G]被稱為是全控制邊臨界的，或者說[γtEC]，如果對于任意的邊[e∈E（G）≠?]，都有[γt（G+e）<γt（G）]，見文獻[5]。如果圖[G]是[γtEC]且[γt（G）=k]，則稱[G]是[kt]-臨界的。

1? ? ?研究背景

1.1? ?直徑為2-臨界圖猜想

圖[G]被稱為是直徑為2-臨界圖，如果它的直徑是2，且任意刪掉一條邊直徑都會增加。在文獻[6]中，Plesnik注意到所有已知的極小的直徑為2的圖，它們的邊數(shù)都小于等于[n24]，并且當圖為完全二部圖[Kn2，n2]的時候，其邊數(shù)可以達到上界[n24]。Murty 和 Simon也分別獨立地發(fā)現(xiàn)了這個事實，并敘述為如下的Murty-Simon 猜想：

猜想 1? ?若[G]是一個直徑為2-臨界圖，設(shè)它的點數(shù)為[n]且邊數(shù)為[m]，則[m≤n24]，等號成立當且僅當[G]是完全二部圖[Kn2，n2]。

為了證明這個猜想，人們做了很多的工作。在文獻[6]中，Plesnik 證明了如果[G]是有[n] 個點和[m]條邊的直徑為 2-臨界圖，則有[m<3n（n-1）/8]。不久后，Caccetta 和 H?ggkvist 在文獻[7]中得到了一個更強的結(jié)論，證明了[m<0.27n2]。Fan證明了當[n≤24]和[n=26]的時候，猜想是成立的;而當[n≥25]的時候，他證明了[m<0.2532n2]，見文獻[8]。Füredi在文獻[9]中證明了當[n]足夠大的時候猜想是成立的，也即當[n>n0]的時候，其中[n0]是一個非常大的數(shù)，大概是2的[1014]次方。

1.2? ?全控制邊臨界圖猜想

在文獻[5]中，Haynes等人首次開展了對全控制邊臨界圖的研究。在此文獻中還證明了在圖上任意加一條邊最多使得此圖的全控制數(shù)減2。設(shè)[G]是全控制邊臨界圖，滿足[γt（G）=k]且對于任意的邊[e∈E（G）]，有[γt（G+e）=k-2]，則稱G是[kt]-超臨界圖。Hanson 和 Wang 首次發(fā)現(xiàn)了直徑為 2-臨界圖和全控制邊臨界圖之間的關(guān)系。

定理 1.1? ? 一個圖是直徑為2-臨界圖當且僅當它的補圖是[3t]-臨界圖或者是[4t]-超臨界圖[10]

在文獻[11]中，Haynes等人對[4t]-超臨界圖做了一個刻畫。

定理 1.2? ? 圖[G]是[4t]-超臨界的當且僅當[G]是兩個完全圖的不交并

因此，Murty-Simon猜想對補圖是[4t]-超臨界圖的直徑為 2-臨界圖是成立的。故而，根據(jù)定理1.1和1.2，證明猜想1等價于證明下面的猜想2。

猜想 2? ?如果[G]是一個[3t]-臨界圖，設(shè)其點數(shù)為[n]且邊數(shù)為[m]，則[m>n（n-2）/4]。

猜想2已經(jīng)被證明對于若干圖類是成立的，如： 直徑為3的[3t]-臨界圖[12]，連通度至多為3的[3t]-臨界圖[13]，claw-free的[3t]-臨界圖[14]，[C4]-free的[3t]-臨界圖[15]和diamond-free的[3t]-臨界圖[16]。

定理 1.3? ? 下列結(jié)論是成立的

（1）猜想2對直徑為3的[3t]-臨界圖是成立的;

（2）猜想2對連通度至多為3的[3t]-臨界圖是成立的;

（3）猜想2對claw-free，[C4]-free和diamond-free的[3t]-臨界圖是成立的。

1.3? ?主要結(jié)果

在本文中，首先證明了[3t]-臨界圖的獨立數(shù)[α（G）]一定小于等于[δ（G）+2]。最后，證明了對于獨立數(shù)取到最大值的[3t]-臨界圖，猜想2是成立的。

定理 1.4? ?設(shè)[G]是一個[3t]-臨界圖，則有[α（G）≤δ（G）+2]。

定理 1.5? ?設(shè)[G]是一個[3t]-臨界圖且滿足[α（G）=δ（G）+2]，則有猜想2是成立的。

2? ? ?[3t]-臨界圖的相關(guān)定義和性質(zhì)

本部分首先介紹[3t]-臨界圖的相關(guān)定義和一些已有的結(jié)果，可參見文獻[12]。最后，證明在下面要用到的一個非常重要的結(jié)論。

設(shè)[G=（V，E）]是一個圖。若[X]和[Y]是[V]的兩個子集，則用[[X，Y]]來表示圖[G]中的兩個端點分別在[X]和[Y]中的所有的邊組成的集合，并且用[e（X，Y）]來表示[[X，Y]]中的邊數(shù)，特別地，用[e（X）]來表示誘導(dǎo)子圖[G[X]]中的邊數(shù)。如果[X={x}]或者[Y={y}]，則也簡記為[[x，Y]]或者[[X，y]]。用[X＼Y]表示屬于子集[X]但不屬于子集[Y]的所有的點構(gòu)成的集合。對于子集[S]，[X?V]，如果[X?N[S]]（或者[X?N（S）]），則稱[S]控制[X]，記為[S?X]（或者[S]全控制 [X]，記為[S?tX]）。如果[S={s}]或者[X={x}]，則也簡記為[s?X]或者[S?x]。若[S?V]（或者[S?tV]），則稱[S]是[G]的一個控制集（或者全控制集），且記為[S?G]（或者[S?tG]）。

定義 2.1? ?設(shè)[G=（V，E）]是一個[3t]-臨界圖。注意到，對于任意的邊[e∈E（G）≠?]，有[γt（G+e）=2]。于是，存在邊[xy∈E（G+e）]，使得在[G+e]中，[{x，y}?tV]，這樣的邊[xy]可能不是唯一的。然而，從中選擇一條邊[xy]且稱它為[uv]的擬邊，簡記為[q.e.]，并且記為[qe（uv）=xy]。在不至于引起混淆的情況下，也用[qe（uv）]來表示[V（qe（uv））（={x，y}）]。注意到[{x，y}]至少要包含[e]的一個端點。

定義 2.2? ?設(shè)[e=uv]是[G]的一條邊使得在[G]中恰有一個點[w]既不與[u]相連也不與[v]相連，則稱[w]是[u]和[v]的唯一的非鄰域點，記為[un（e）=w]。

定義 2.3? ?設(shè)[S?V]，且[u]和[v]是子集[S]的兩個不相連的點，則稱[uv]是[S]中的一條缺失邊。而且，如果在子集[S]中不存在缺失邊，則稱[S]是滿的。

定義 2.4? ?設(shè)[S]是一個點集合使得在[S]的缺失邊和擬邊構(gòu)成的集合之間有一個一一對應(yīng)。稱這樣的對應(yīng)為擬對應(yīng)，同時稱[S]誘導(dǎo)了一個擬團。注意到一條擬邊必有一個端點在集合[S]外，且一個擬團[S]同時包含[G[S]]中的邊和與[G[S]]的缺失邊相關(guān)聯(lián)的擬邊。類似的，如果集合[A]和[B]之間的所有缺失邊構(gòu)成的集合存在一個擬對應(yīng)，則稱[[A，B]]是擬滿的。

命題 2.5? ?設(shè)[G=（V，E）]是一個[3t]-臨界圖。如果[xy∈E]是[G]的某條缺失邊的擬邊，則[xy]最多是兩條缺失邊的擬邊，也即[xz]和[yz]，其中[z=un（xy）]。[12]

命題 2.6? ?設(shè)[i+j=n]，其中[i]和[j]為非負整數(shù)，則有下列等式成立[12]

[i2+j2=n（n-2）4+（i-j）24]。

下面兩個命題討論了[3t]-臨界圖的性質(zhì)，并且得到了[3t]-臨界圖的直徑的界。

命題 2.7? ?若[G]是一個[3t]-臨界圖，則[2≤diam（G）]

[≤3]。[5]

命題 2.8? ?對于任意一個[3t]-臨界圖[G]和它的任意兩個不相連的點[u]和[v]，則必有下列情形之一成立： [5]

（1）[{u，v}?G];

（2）存在[w∈N（u）]使得[{u，w}]控制[G-v]，但是不控制[v]，記為[uw?v];

（3）存在[w∈N（v）]使得[{v，w}]控制[G-u]，但是不控制[u]，記為[vw?u]。

下面兩個結(jié)論實際上是關(guān)于3-臨界圖的（見文獻[4]中引理2，文獻[17]中定理2.9以及文獻[18]中定理1.5），通過查看相應(yīng)的證明，容易驗證這兩個結(jié)論對于[3t]-臨界圖仍然是成立的。

命題2.9? ?設(shè)[G]是一個[3t]-臨界圖且滿足[α（G）≥3]。如果[W]是[G]的一個獨立集且有[|W|=k≥3]，則存在[W]的一個有序點列[w1，w2，.，wk]和[G-W]的一條路[z1，z2，.，zk-1]使得對于任意的[1≤i≤k-1]，有[wizi?wi+1]成立。

命題 2.10? ?設(shè)[G]是一個[3t]-臨界圖且滿足[α（G）=δ（G）+2]，則

（Ⅰ）[G]的最小度點是唯一的，設(shè)為[xδ];

（Ⅱ）[G]的每一個最大獨立集都包含[xδ]，且[N（xδ）]是一個團。

最后，證明一個將在面非常有用的命題。

命題 2.11? ?設(shè)[G]是有[n]個點和[m]條邊的[3t]-臨界圖，且滿足[δ（G）≤α（G）≤δ（G）+2]，其中[δ（G）≥4]。如果[G]不是正則圖且[m≥δ+1? ?2+n-δ-1? ? ? 2]，則有[m>n（n-2）/4]。

證明：根據(jù)命題 2.6，有

[m≥δ+1? ?2+n-δ-1? ? ? 2=n（n-2）4+（n-2δ-2）24]。

因此，只需在[n]為偶數(shù)時，考慮[δ=n-22]的情形，而當[n]為奇數(shù)時，考慮[δ=n-12]或者[n-32]的情形。下面僅就[α=δ+2]和[δ]做詳細的討論，對于[α=δ+1]的情形，因為它與[α=δ]的討論過程類似，故而省略此種情形的討論。

先設(shè)[α=δ+2]。由命題 2.10（Ⅰ），知道最小度點是唯一的。因為[δ≥4]，根據(jù)[δ]的三種可能性，即[n]為偶數(shù)時，[δ=n-22]，[n]為奇數(shù)時，[δ=n-12]或者[n-32]，可得n ≥ 9。于是，[m≥δ+（n-1）（δ+1）2]

[=nδ+n-12≥n（n-32）+n-12≥n（n-2）4+1>n（n-2）4]。

再設(shè)[α=δ]。因為[G]不是正則圖，若[δ=n-12]或者[n-22]，則結(jié)論顯然成立。故而，只需考慮[δ=n-32]的情形，也即[n=2δ+3]。注意到[δ≥4]，有[n≥11]。設(shè)[I]是一個最大獨立集。根據(jù)命題2.9，存在[I]的一個有序點列[w1，w2，.，wδ]和一條路[A=（z1，z2，.，zδ-1）]使得

[wizi?wi+1]，對于任意的[1≤i≤δ-1]。? ? （1）

由Eq（1），有[e（I，A）=（δ-1）2]。因為[n=2δ+3]，故可設(shè)[V（G）＼（I?A）={yj|1≤j≤4}]。再由Eq（1），對任意的[1≤i≤δ-1]，每一個點[yj]至少與[{wi，zi}]中的一個點相連。因此，對于任意的[1≤j≤4]，可得[e（yj，（I?A）＼{wδ}）≥δ-1]。由于[deg（wδ，A）=δ-2]，故在[V（G）＼（I?A）]在中還至少存在兩個點與[wδ]相連，設(shè)為[y1]和[y2]。于是，當[j=1，2]時，有[e（yj，I?A）≥δ]。而且，因為[A]是一條路，可得[e（A）≥δ-2]。因此，結(jié)合 n ≥ 11 和[δ=n-32]，可以得到

[m≥e（I，A）+j=12e（yj，I?A）+e（y3，I?A）+deg（y4）+e（A）? ≥（δ-1）2+2δ+（δ-1）+δ+（δ-2）=δ2+3δ-2>n（n-2）4+1>n（n-2）4。]

3? ? ?定理1.4和1.5的證明

設(shè)[G=（V，E）]是有[n]個點和[m]條邊的[3t]-臨界圖。注意到對于任意的[3t]-臨界圖，它的最小度點不一定是唯一的，任取一個最小度點并記為[xδ]。根據(jù)定理1.3（1）和命題2.7，可設(shè)[diam（G）=2]。更進一步地，定理1.3 （2）意味著只需要考慮[δ（G）≥4]的情形。下面證明定理1.4，對于任意一個[3t]-臨界圖[G]，它的獨立數(shù)[α（G）]最多是[δ（G）+2]。

定理 1.4? ?設(shè)[G]是一個[3t]-臨界圖，則有[α（G）≤δ（G）+2]

證明：不失一般性，設(shè)[α（G）：=k≥3]。設(shè)[W]是[G]的一個最大獨立集，故有 [W=k]。根據(jù)命題 2.9，則存在[G]的一個有序點列[w1，w2，. ，wk]和一條路[A=（z1，z2. zk-1）]使得

[wizi?wi+1]，對于任意的[1≤i≤k-1]。 （2）

由Eq（2），容易看出[A?N（w1）]，且對于任意的[2≤i≤k]，有[A＼{zi-1}?N（wi）]，故有

[deg（wi）≥k-2]，對于任意的[1≤i≤k]。 （3）

而且，有[W＼{wi+1}?N（zi）]，從而

[deg（zi）≥k-1]，對于任意的[1≤i≤k-1]。 （4）

任取[v∈V（G）＼（W?A）]。從Eq（2），知道對于任意的[1≤i≤k-1]，點[v]至少與每對[{wi，zi}]中的一個點相連。于是

[deg（v）≥k-1]，對于任意的[v∈V（G）＼（W?A）]。 （5）

結(jié)合Eq（3），Eq（4）和Eq（5），可得[δ（G）≥k-2]，也即[α（G）≤δ（G）+2]，證畢。

定理1.5? ?設(shè)[G]是有[n]個點和[m]條邊的[3t]-臨界圖，且[α（G）=δ（G）+2]，則[m>n（n-2）/4]

證明：根據(jù)命題2.10，有[xδ]是唯一的最小度點且它的鄰域[N（xδ）]是一個團。設(shè)[S=V（G）＼N[xδ]]。首先，證明點集[S]是一個擬團。為了證明[S]是一個擬團，只需證明在[S]中不同的缺失邊關(guān)聯(lián)的擬邊必不相同。設(shè)[u]和[v]是[S]中的任意兩個不相連的點，現(xiàn)在考慮[G+uv]。因為[u，v≯xδ]，根據(jù)命題2.8，可得[uw?v]或者[vw?u]，其中為了控制點[xδ]，有[w∈N（xδ）]。不失一般性，設(shè)[uw?v]。因此，可以把邊[uw]與[S]中的缺失邊[uv ]相關(guān)聯(lián)。從命題2.5，知道在[S]中[uv]是僅有的可把[uw]作為擬邊的缺失邊，也即在[S]中不同的缺失邊關(guān)聯(lián)的擬邊必不相同。因此，[S]是一個擬團?，F(xiàn)在，有[N[xδ]]是一個團而[S]是一個擬團，其中[|S|=n-δ-1]。故而可得，[m≥δ+12+n-δ-12]。再根據(jù)命題2.11，可得 [m>n（n-2）/4]，證畢。

[參考文獻]

[1] J.A. Bondy，U.S.R. Murty. Graph Theory with Applications[M]. New York： Elsevier，1976.

[2] T.W. Haynes，S.T. Hedetniemi，P.J. Slater（Eds.）. Fundamentals of Domination in Graphs[M]. New York： Marcel Dekker，Inc.，1998.

[3] T.W. Haynes，S.T. Hedetniemi，P.J. Slater（Eds.）. Domination in Graphs： Advanced Topics[M]. New York： Marcel Dekker，Inc.，1998.

[4] D.P. Sumner，P. Blitch. Domination critical graphs[J]. Journal of Combinatorial Theory，Series B，1983（34）： 65–76.

[5] T.W. Haynes，C.M. Mynhardt，L.C. van der Merwe. Total domination edge critical graphs[J]. Utilitas Mathematica，1998（54）： 229–240.

[6] J. Plesnik. Critical graphs of given diameter[J]. Acta Fac. Rerum Natur. Univ. Comenian. Math.，1975（30）： 71–93.

[7] L. Caccetta，R. H?ggkvist. On diameter critical graphs[J]. Discrete Mathematics，1979，28 （3）： 223-229.

[8] G. Fan. On diameter 2-critical graphs[J]. Discrete Mathematics，1987（67）： 235-240.

[9] Z. Füredi. The maximal number of edges in a minimal graph of diameter 2[J]. Journal of Graph Theory，1992（16）： 81-98.

[10] D. Hanson，P. Wang. A note on extremal total domination edge critical graphs[J]. Utilitas Mathematica，2003（63）： 89-96.

[11] T. W. Haynes，C. M. Mynhardt， L. C. van der Merwe. Criticality index of total domination[J]. Congressus Numerantium，1998（131）： 67-73.

[12]? T.W. Haynes，M.A. Henning，L. Merwec，et al. On a conjecture of Murty and Simon on diameter 2-critical graphs[J]. Discrete Mathematics，2011（311）： 1918-1924.

[13] T.W. Haynes，M.A. Henning，A. Yeo. On a conjecture of Murty and Simon on diameter two critical graphs II [J]. Discrete Mathematics，2012（312）： 315-323.

[14] T.W. Haynes，M.A. Henning，A. Yeo. A proof of a conjecture on diameter two critical graphs whose complements are claw-free[J]. Discrete Optimization，2011（8）： 495-501.

[15] T. W. Haynes，M. A. Henning. A characterization of diameter-2-critical graphs with no antihole of length four[J]. Central European Journal of Mathematics，2012，10（3）： 1125-1132.

[16]? T. W. Haynes，M. A. Henning. A characterization of diameter-2-critical graphs whose complements are diamond-free[J]. Discrete Applied Mathematics，2012（160）： 1979-1985.

[17] O. Favaron，F(xiàn). Tian，L. Zhang. Independence and hamiltonicity in 3-domination-critical graphs[J]. Journal of Graph Theory，1997（25）： 173-184.

[18] F. Tian，B. Wei，L. Zhang. Hamiltonicity in 3-domination-critical graphs with α = δ + 2[J]. Discrete Applied Mathematics，1999（92）： 57-70.