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

徐文琴

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

【关键词】   直径为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     基本概念

关于图论中的符号和术语建议读者参考文献[1]。设[G=（V（G），E（G））]是一个图，其中顶点集为[V（G）]，边集为[E（G）]。设[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）]所诱导的子图，且设[G-S=G[V（G）-S]]。用[deg（v，S）]来表示子集[S?V（G）]中与[v] 相连的点数，特别地，如果[S=V（G）]，则把它简记为[deg（v）]。符号[α（G）]和[δ（G）]分别表示图[G]的独立数和最小度。通常还把[α（G）]和[δ（G）]分别简记为[α]和[δ]。图[G]的所有点对的最长距离称为图[G]的直径，记为[diam（G）]。用[S]来表示集合[S]的基数。

控制集理论由于其广泛的应用和理论意义，故而成为图论中非常重要的一部分，见文献 [2，3]。如果对于任意的[v∈V（G）]，有[v∈S]或者[v]与[S]中的某个点相连，也即[N[S]=V（G）]，则子集[S?V（G）]称为是[G]的控制集，记为[DS]。图[G]的控制数指的是[G]的所有控制集的最小基数，记为[γ（G）]。控制边临界图的概念则是由Sumner和Blitch在文献[4]中引进的。称图[G]是控制边临界的，或者[γEC]，如果对于任意一条边[e∈E（G）]，有[γ（G+e）<γ（G）]。若图[G]是[γEC]且[γ（G）=k]，则称[G]是 [k]-临界的。设[G]是一个没有孤立点的图，若[S]是[G]的一个子集满足[G]的每一个点都与[S]中的某一个点相连，也即[N（S）=V（G）]，则称[S]是[G]的一个全控制集，记为[TDS]。注意到每一个没有孤立点的图都至少有一个[TDS]，因为[S=V（G）]就是一个全控制集。图[G]的所有[TDS]的最小基数就称作为全控制数，记为[γ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的图，它们的边数都小于等于[n24]，并且当图为完全二部图[Kn2，n2]的时候，其边数可以达到上界[n24]。Murty 和 Simon也分别独立地发现了这个事实，并叙述为如下的Murty-Simon 猜想：

猜想 1   若[G]是一个直径为2-临界图，设它的点数为[n]且边数为[m]，则[m≤n24]，等号成立当且仅当[G]是完全二部图[Kn2，n2]。

为了证明这个猜想，人们做了很多的工作。在文献[6]中，Plesnik 证明了如果[G]是有[n] 个点和[m]条边的直径为 2-临界图，则有[m<3n（n-1）/8]。不久后，Caccetta 和 H?ggkvist 在文献[7]中得到了一个更强的结论，证明了[m<0.27n2]。Fan证明了当[n≤24]和[n=26]的时候，猜想是成立的;而当[n≥25]的时候，他证明了[m<0.2532n2]，见文献[8]。Füredi在文献[9]中证明了当[n]足够大的时候猜想是成立的，也即当[n>n0]的时候，其中[n0]是一个非常大的数，大概是2的[1014]次方。

1.2   全控制边临界图猜想

在文献[5]中，Haynes等人首次开展了对全控制边临界图的研究。在此文献中还证明了在图上任意加一条边最多使得此图的全控制数减2。设[G]是全控制边临界图，满足[γt（G）=k]且对于任意的边[e∈E（G）]，有[γt（G+e）=k-2]，则称G是[kt]-超临界图。Hanson 和 Wang 首次发现了直径为 2-临界图和全控制边临界图之间的关系。

定理 1.1    一个图是直径为2-临界图当且仅当它的补图是[3t]-临界图或者是[4t]-超临界图[10]

在文献[11]中，Haynes等人对[4t]-超临界图做了一个刻画。

定理 1.2    图[G]是[4t]-超临界的当且仅当[G]是两个完全图的不交并

因此，Murty-Simon猜想对补图是[4t]-超临界图的直径为 2-临界图是成立的。故而，根据定理1.1和1.2，证明猜想1等价于证明下面的猜想2。

猜想 2   如果[G]是一个[3t]-临界图，设其点数为[n]且边数为[m]，则[m>n（n-2）/4]。

猜想2已经被证明对于若干图类是成立的，如： 直径为3的[3t]-临界图[12]，连通度至多为3的[3t]-临界图[13]，claw-free的[3t]-临界图[14]，[C4]-free的[3t]-临界图[15]和diamond-free的[3t]-临界图[16]。

定理 1.3    下列结论是成立的

（1）猜想2对直径为3的[3t]-临界图是成立的;

（2）猜想2对连通度至多为3的[3t]-临界图是成立的;

（3）猜想2对claw-free，[C4]-free和diamond-free的[3t]-临界图是成立的。

1.3   主要结果

在本文中，首先证明了[3t]-临界图的独立数[α（G）]一定小于等于[δ（G）+2]。最后，证明了对于独立数取到最大值的[3t]-临界图，猜想2是成立的。

定理 1.4   设[G]是一个[3t]-临界图，则有[α（G）≤δ（G）+2]。

定理 1.5   设[G]是一个[3t]-临界图且满足[α（G）=δ（G）+2]，则有猜想2是成立的。

2     [3t]-临界图的相关定义和性质

本部分首先介绍[3t]-临界图的相关定义和一些已有的结果，可参见文献[12]。最后，证明在下面要用到的一个非常重要的结论。

设[G=（V，E）]是一个图。若[X]和[Y]是[V]的两个子集，则用[[X，Y]]来表示图[G]中的两个端点分别在[X]和[Y]中的所有的边组成的集合，并且用[e（X，Y）]来表示[[X，Y]]中的边数，特别地，用[e（X）]来表示诱导子图[G[X]]中的边数。如果[X={x}]或者[Y={y}]，则也简记为[[x，Y]]或者[[X，y]]。用[X＼Y]表示属于子集[X]但不属于子集[Y]的所有的点构成的集合。对于子集[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   设[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   设[e=uv]是[G]的一条边使得在[G]中恰有一个点[w]既不与[u]相连也不与[v]相连，则称[w]是[u]和[v]的唯一的非邻域点，记为[un（e）=w]。

定义 2.3   设[S?V]，且[u]和[v]是子集[S]的两个不相连的点，则称[uv]是[S]中的一条缺失边。而且，如果在子集[S]中不存在缺失邊，则称[S]是满的。

定义 2.4   设[S]是一个点集合使得在[S]的缺失边和拟边构成的集合之间有一个一一对应。称这样的对应为拟对应，同时称[S]诱导了一个拟团。注意到一条拟边必有一个端点在集合[S]外，且一个拟团[S]同时包含[G[S]]中的边和与[G[S]]的缺失边相关联的拟边。类似的，如果集合[A]和[B]之间的所有缺失边构成的集合存在一个拟对应，则称[[A，B]]是拟满的。

命题 2.5   设[G=（V，E）]是一个[3t]-临界图。如果[xy∈E]是[G]的某条缺失边的拟边，则[xy]最多是两条缺失边的拟边，也即[xz]和[yz]，其中[z=un（xy）]。[12]

命题 2.6   设[i+j=n]，其中[i]和[j]为非负整数，则有下列等式成立[12]

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

下面两个命题讨论了[3t]-临界图的性质，并且得到了[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]。

下面两个结论实际上是关于3-临界图的（见文献[4]中引理2，文献[17]中定理2.9以及文献[18]中定理1.5），通过查看相应的证明，容易验证这两个结论对于[3t]-临界图仍然是成立的。

命题2.9   设[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   设[G]是一个[3t]-临界图且满足[α（G）=δ（G）+2]，则

（Ⅰ）[G]的最小度点是唯一的，设为[xδ];

（Ⅱ）[G]的每一个最大独立集都包含[xδ]，且[N（xδ）]是一个团。

最后，证明一个将在面非常有用的命题。

命题 2.11   设[G]是有[n]个点和[m]条边的[3t]-临界图，且满足[δ（G）≤α（G）≤δ（G）+2]，其中[δ（G）≥4]。如果[G]不是正则图且[m≥δ+1   2+n-δ-1      2]，则有[m>n（n-2）/4]。

证明：根据命题 2.6，有

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

因此，只需在[n]为偶数时，考虑[δ=n-22]的情形，而当[n]为奇数时，考虑[δ=n-12]或者[n-32]的情形。下面仅就[α=δ+2]和[δ]做详细的讨论，对于[α=δ+1]的情形，因为它与[α=δ]的讨论过程类似，故而省略此种情形的讨论。

先设[α=δ+2]。由命题 2.10（Ⅰ），知道最小度点是唯一的。因为[δ≥4]，根据[δ]的三种可能性，即[n]为偶数时，[δ=n-22]，[n]为奇数时，[δ=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]。

再设[α=δ]。因为[G]不是正则图，若[δ=n-12]或者[n-22]，则结论显然成立。故而，只需考虑[δ=n-32]的情形，也即[n=2δ+3]。注意到[δ≥4]，有[n≥11]。设[I]是一个最大独立集。根据命题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]，故可设[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δ]相连，设为[y1]和[y2]。于是，当[j=1，2]时，有[e（yj，I?A）≥δ]。而且，因为[A]是一条路，可得[e（A）≥δ-2]。因此，结合 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的证明

设[G=（V，E）]是有[n]个点和[m]条边的[3t]-临界图。注意到对于任意的[3t]-临界图，它的最小度点不一定是唯一的，任取一个最小度点并记为[xδ]。根据定理1.3（1）和命题2.7，可设[diam（G）=2]。更进一步地，定理1.3 （2）意味着只需要考虑[δ（G）≥4]的情形。下面证明定理1.4，对于任意一个[3t]-临界图[G]，它的独立数[α（G）]最多是[δ（G）+2]。

定理 1.4   设[G]是一个[3t]-临界图，则有[α（G）≤δ（G）+2]

证明：不失一般性，设[α（G）：=k≥3]。设[W]是[G]的一个最大独立集，故有 [W=k]。根据命题 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）

结合Eq（3），Eq（4）和Eq（5），可得[δ（G）≥k-2]，也即[α（G）≤δ（G）+2]，证毕。

定理1.5   设[G]是有[n]个点和[m]条边的[3t]-临界图，且[α（G）=δ（G）+2]，则[m>n（n-2）/4]

证明：根据命题2.10，有[xδ]是唯一的最小度点且它的邻域[N（xδ）]是一个团。设[S=V（G）＼N[xδ]]。首先，证明点集[S]是一个拟团。为了证明[S]是一个拟团，只需证明在[S]中不同的缺失边关联的拟边必不相同。设[u]和[v]是[S]中的任意两个不相连的点，现在考虑[G+uv]。因为[u，v≯xδ]，根据命题2.8，可得[uw?v]或者[vw?u]，其中为了控制点[xδ]，有[w∈N（xδ）]。不失一般性，设[uw?v]。因此，可以把边[uw]与[S]中的缺失边[uv ]相关联。从命题2.5，知道在[S]中[uv]是仅有的可把[uw]作为拟边的缺失边，也即在[S]中不同的缺失边关联的拟边必不相同。因此，[S]是一个拟团。现在，有[N[xδ]]是一个团而[S]是一个拟团，其中[|S|=n-δ-1]。故而可得，[m≥δ+12+n-δ-12]。再根据命题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. 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.