引言

图论不变量是一些特殊的拓扑指标，常被用来描述某些化学分子结构图的基础性质。基于顶点间距离的不变量如Wiener指标^[1-3]、度距离指标^[4-6]等都得到学者们的广泛关注，并得出大量相关结论。Gupta等^[7]于2002年首次提出了新的图论不变量，即离心距离指标(EDS)。此后，学者们对树、单圈图和仙人掌图的EDS做了大量研究。Yu等^[8]刻画出具有最小、第二小ξ^d(G)值的单圈图，并计算出树的最小离心距离指标；Ilić等^[9]确定了具有最大ξ^d(G)值的树，并对EDS与其他图论不变量之间的关系作了一系列的探究；Hua等^[10]得出了n个顶点仙人掌图的ξ^d(G)值的下确界。

三圈图是一类具有特殊结构的图，当且仅当图G的边数等于顶点数加2时，图G就是一个三圈图。在对三圈图的EDS的研究过程中，Li等^[9]通过确定EDS与边数m(m=|E(G)|)之间的关系，最终得到了三圈图的最小ξ^d(G)值。但是文献[11]的方法不具一般性和适用性，不能被用来研究更一般图的离心距离指标。本文构思了一种完全不同于文献[11]的新方法，首先研究了文献[12]中3种移边变换对离心距离指标的数值大小的影响，然后基于这3种变换，利用数学归纳法得到了三圈图的最小ξ^d(G)值以及最小值所对应的特殊结构的三圈图。

1 特定移边变换对ξ^d(G)的影响

对于任意连通图G=(V, E)，定义图G的EDS^[7]为

$ {\xi ^d}\left( G \right) = \sum\limits_{\left\{ {u,v} \right\} \subset V\left( G \right)} {\left( {{\varepsilon _G}\left( u \right) + {\varepsilon _G}\left( v \right)} \right){d_G}\left( {u,v} \right)} $

其中距离d_G(u, v)表示顶点u和v之间的最短路长度，离心率ε_G(·)表示对应顶点到图G所有其他顶点的距离最大值。

Li等^[12]在研究离心阻尼距离指标(ERDS)的数学性质时刻画了3种移边变换，具体内容如下。

第一变换 给定一个简单连通图H和一个星图(中心为v，叶子为v₁, v₂, …, v_p+1)如图 1(a)所示。对于图H中的某一顶点u，将顶点v_p+1和u重合，记新得到的图为G。则第一变换G→G′为

$ G' = G - \left\{ {v{v_1},v{v_2}, \cdots ,v{v_p}} \right\} + \left\{ {u{v_1},u{v_2}, \cdots ,u{v_p}} \right\} $

第二变换 给定一个简单连通图G如图 1(b)，设顶点u在图G中具有p个悬挂点(u₁, u₂, …, u_p)，顶点v(不同于顶点u)在图G中具有q个悬挂点(v₁, v₂, …, v_q)。则第二变换G→G′和G→G″分别为

$ G' = G - \left\{ {v{v_1},v{v_2}, \cdots ,v{v_q}} \right\} + \left\{ {u{v_1},u{v_2}, \cdots ,u{v_q}} \right\} $

$ G'' = G - \left\{ {u{u_1},u{u_2}, \cdots ,u{u_p}} \right\} + \left\{ {v{u_1},v{u_2}, \cdots ,v{u_p}} \right\} $

第三变换给定简单连通图G如图 1(c)，n>3，e=uv是图G中的一条非悬挂割边。设

$ G - e = {G_1} \cup {G_2},u \in {V_{{G_1}}},v \in {V_{{G_2}}} $

将图 1(c)中的G→G′变换记为第三变换。

本文通过计算验证了这3种移边变换对ξ^d(G)的数值大小的影响，同时给出下列3条相应的定理。

定理1  设图G和图G′分别为图 1(a)中的两个图，则ξ^d(G′)≤ξ^d(G)，当且仅当图G是以顶点v为中心的星图时等号成立。

定理2  设图G、图G′和图G″分别为图 1(b)中的图，则ξ^d(G′) < ξ^d(G)或ξ^d(G″) < ξ^d(G)。

定理3 给定简单连通图G(n>3)，e=uv是图G中的一条非悬挂割边，对图G中的边e做第三变换得到图G′，则ξ^d(G′) < ξ^d(G)。

由于定理1~3的证明思路、证明方法与文献[10]非常相似，所以在此只给出定理1的详细证明。

为了方便计算，在后续证明中，对于图G或图G′中任意两点x和y，假设ε(x):=ε_G(x)或ε′(x):=ε_G′(x)，d(x, y):=d_G(x, y)或d′(x, y):=d_G′(x, y)

证明(定理1)

对于图 1中的图G和G′，假设|V(H)|>1，W={v₁, v₂, …, v_p}，可以得到

$ \left\{ \begin{array}{l} V\left( G \right) = V\left( {G'} \right),\varepsilon \left( v \right) = \varepsilon '\left( v \right)\\ \forall x \in V\left( H \right),\varepsilon \left( x \right) \ge \varepsilon '\left( x \right)\\ \forall y \in W,\varepsilon \left( y \right) = \varepsilon '\left( y \right) + 1 \end{array} \right. $

(1)

$ \left\{ \begin{array}{l} \forall x,y \in V\left( H \right),d\left( {x,y} \right) = d'\left( {x,y} \right)\\ \forall x,y \in W,d\left( {x,y} \right) = d'\left( {x,y} \right) \end{array} \right. $

(2)

因为式(1)和式(2)成立，所以有

$ \begin{array}{l} {\xi _1}: = \left( {\sum\limits_{\left\{ {x,y} \right\} \subseteq {V_H}} + \sum\limits_{\left\{ {x,y} \right\} \subseteq W} {} } \right)\left[ {\left( {\varepsilon \left( x \right) + \varepsilon \left( y \right)} \right)} \right.\\ \left. {d\left( {x,y} \right) - \left( {\varepsilon '\left( x \right) + \varepsilon '\left( y \right)} \right)d'\left( {x,y} \right)} \right] + \left[ {\sum\limits_{x \in {V_H}\backslash \left\{ u \right\},y \in W} + } \right.\\ \left. {\sum\limits_{x \in {V_H},y = v} {} } \right)\left[ {\left( {\varepsilon \left( x \right) + \varepsilon \left( y \right)} \right)d\left( {x,y} \right) - \left( {\varepsilon '\left( x \right) + } \right.} \right.\\ \left. {\left. {\varepsilon '\left( y \right)} \right)d'\left( {x,y} \right)} \right] > 0 \end{array} $

$ \begin{array}{l} {\xi _2}: = \sum\limits_{x \in W,y = u} {\left( {\varepsilon \left( x \right) + \varepsilon \left( y \right)} \right)d\left( {x,y} \right)} - \\ \sum\limits_{x \in W,y = u} {\left( {\varepsilon '\left( x \right) + \varepsilon '\left( y \right)} \right)d'\left( {x,y} \right)} + \sum\limits_{x \in W,y = v} {\left( {\varepsilon \left( x \right) + } \right.} \\ \left. {\varepsilon \left( y \right)} \right)d\left( {x,y} \right) - \sum\limits_{x \in W,y = v} {\left( {\varepsilon '\left( x \right) + \varepsilon '\left( y \right)} \right)d'\left( {x,y} \right)} = \\ \left| W \right|\left[ {2\left( {\varepsilon \left( u \right) + \varepsilon \left( {{v_1}} \right)} \right) - \left( {\varepsilon '\left( u \right) + \varepsilon '\left( {{v_1}} \right)} \right)} \right] + \left| W \right|\\ \left[ {\left( {\varepsilon \left( v \right) + \varepsilon \left( {{v_1}} \right)} \right) - 2\left( {\varepsilon '\left( v \right) + \varepsilon '\left( {{v_1}} \right)} \right)} \right] \ge 3\left| W \right|\left( \varepsilon \right.\\ \left. {\left( {{v_1}} \right) + \varepsilon '\left( {{v_1}} \right)} \right) + \left| W \right|\left( {2\varepsilon \left( u \right) - 2\varepsilon '\left( v \right) + \varepsilon \left( v \right) - } \right.\\ \left. {\varepsilon '\left( u \right)} \right) \ge 3\left| W \right| + \left| W \right|\left( {\varepsilon \left( u \right) - \varepsilon '\left( v \right)} \right) = \left| W \right|\left( {\varepsilon \left( u \right) - } \right.\\ \left. {\varepsilon \left( v \right) + 3} \right) \end{array} $

如果ε_H(u)=1，那么ε(u)=ε(v)=2，则

$ \varepsilon \left( u \right) - \varepsilon \left( v \right) + 3 > 0 $

如果ε_H(u)=r≥2，那么ε(u)=r，ε(v)=r+1，则

$ \varepsilon \left( u \right) - \varepsilon \left( v \right) + 3 > 0 $

由此可知ξ₂>0。根据ξ^d(G)的定义可以得到

$ {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) = {\xi _1} + {\xi _2} > 0 $

显然，当且仅当|V(H)|=1，即图G是以顶点v为中心的星图时，ξ^d(G)=ξ^d(G′)。

定理1由此得证。证毕。

2 三圈图的最小离心距离指标

对任意三圈图G，其基图$\hat G $是指图G的唯一不包含悬挂点的三圈子图。一般性地，用C_n表示n个顶点构成的圈，用P_n表示n个顶点构成的路。

设图G是具有最小ξ^d值的三圈图，$\hat G $是图G的基图。由定理1~3可知，$\hat G $的内部不存在割边，且图G必然是由(|V(G)|－|V($\hat G $)|)个孤立顶点连接于$\hat G $中的同一顶点构成的。为了便于进一步讨论，将所有图G根据基图的结构分为3大类：

1) T¹(n, r, s, t)={G}，其中r、s、t分别表示图$\hat G $中的3个圈C_r、C_s和C_t，r≥s≥t，且C_r、C_s、C_t彼此之间在图$\hat G $中至多有1个公共顶点；

2) T²(n, x, y, z, w)={G}，其中x, y, z分别表示$\hat G $中连通顶点p和q的3条内部不交的路P_x、P_y和P_z，w表示$\hat G $中连通顶点g和h的路P_w，w≥x≥y≥z，且$\left\{ {g, h} \right\} \subset \bigcup\limits_{i = x, y, z} {V\left( {{P_i}} \right)} $；

3) T³(n, x, y, z, w)={G}，其中x, y, z分别表示$\hat G $中连通顶点p和q的3条内部不交的路P_x、P_y和P_z(x≥y≥z)，w表示$\hat G $中悬挂于顶点g的圈C_w(w≥3)，且$g \in \bigcup\limits_{i = x, y, z} {V\left( {{P_i}} \right)}, V\left( {{C_w}-g} \right) \cap \bigcup\limits_{i = x, y, z} {V\left( {{P_i}} \right)} = \emptyset $。

引理4  若三圈图G∈T¹(7, r, s, t)，则ξ^d(G)≥126；若三圈图G∈T²(5, x, y, z, w)，则ξ^d(G)≥48；若三圈图G∈T³(6, x, y, z, w)，则ξ^d(G)≥83。

证明  显然，如图 2所示，若三圈图G∈T¹(7, r, s, t)，则

$ G \in \left\{ {{T^{1\left( 1 \right)}},{T^{1\left( 2 \right)}}} \right\} $

若三圈图G∈T²(5, x, y, z, w)，则

$ G \in \left\{ {{T^{2\left( 1 \right)}},{T^{2\left( 2 \right)}},{T^{2\left( 3 \right)}}} \right\} $

若三圈图G∈T³(6, x, y, z, w)，则

$ G \in \left\{ {{T^{3\left( 1 \right)}},{T^{3\left( 2 \right)}}} \right\} $

计算可得

$ \left\{ \begin{array}{l} {\xi ^d}\left( {{T^{1\left( 1 \right)}}} \right) = 126,{\xi ^d}\left( {{T^{1\left( 2 \right)}}} \right) = 211\\ {\xi ^d}\left( {{T^{2\left( 1 \right)}}} \right) = 48,{\xi ^d}\left( {{T^{2\left( 2 \right)}}} \right) = 48,{\xi ^d}\left( {{T^{2\left( 3 \right)}}} \right) = 48\\ {\xi ^d}\left( {{T^{3\left( 1 \right)}}} \right) = 83,{\xi ^d}\left( {{T^{3\left( 2 \right)}}} \right) = 124 \end{array} \right. $

由计算结果可知引理4成立。证毕。

引理5  若三圈图G∈T¹(n, r, s, t)，n≥7，则ξ^d(G)≥4n²－9n－7，当且仅当$G \cong {G_3} $时等号成立(其中G₃如图 3所示)。

证明  对n进行归纳。由引理4可知，当n=7时，ξ^d(G)≥126，当且仅当$G \cong {G_3} $时等号成立。假设对任意n－1个顶点的三圈图结论都成立，则只需证明对任意n≥8个顶点的三圈图，结论仍成立。

情况1  若图G中存在悬挂点，不妨取G中任意悬挂点w，顶点w′为w在图G中的唯一邻点。显然有

$ \left\{ \begin{array}{l} \varepsilon \left( w \right) \ge 2,\varepsilon \left( {w'} \right) \ge 1,d\left( {w,w'} \right) = 1\\ \varepsilon \left( a \right) \ge 2,d\left( {a,w} \right) \ge 2,\forall a \in V\left( G \right)\backslash \left\{ {w,w'} \right\} \end{array} \right. $

(3)

记G′=G－w，G′仍是三圈图，由分析可知

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge \varepsilon '\left( a \right),\varepsilon \left( b \right) \ge \varepsilon '\left( b \right),\forall a,b \in V\left( {G'} \right)\\ d\left( {a,b} \right) \ge d'\left( {a,b} \right),\forall a,b \in V\left( {G'} \right)\\ {\xi ^d}\left( {G'} \right) \ge 4{\left( {n - 1} \right)^2} - 9\left( {n - 1} \right) - 7 = \\ \;\;\;\;\;\;\;\;\;\;4{n^2} - 17n + 6 \end{array} \right. $

(4)

因为式(3)和式(4)成立，所以有

$ \begin{array}{l} {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) = \sum\limits_{a,b \in V\left( {G'} \right)} {\left[ {\left( {\varepsilon \left( a \right) + \varepsilon \left( b \right)} \right)} \right.} \\ \left. {d\left( {a,b} \right) - \left( {\varepsilon '\left( a \right) + \varepsilon '\left( b \right)} \right)d'\left( {a,b} \right)} \right] + \left( {\varepsilon \left( {w'} \right) + } \right.\\ \left. {\varepsilon \left( w \right)} \right)d\left( {w',w} \right) + \sum\limits_{a \in V\left( {G'} \right)\backslash \left\{ {w'} \right\}} {\left( {\varepsilon \left( a \right) + \varepsilon \left( w \right)} \right)d\left( {a,} \right.} \\ \left. w \right) \ge 0 + \left( {1 + 2} \right) \times 1 + \left( {n - 2} \right) \times \left( {2 + 2} \right) \times 2 = \\ 8n - 13 \end{array} $

即对于情况1下的三圈图G，有ξ^d(G)≥ξ^d(G′)+8n－13≥4n²－9n－7，当且仅当$G \cong {G_3} $时等号成立。

情况2  若图G中不存在悬挂点，由于n≥8，r+s+t－2=n，且r≥s≥t，则有r≥4。不妨取G中顶点w∈V(C_r)且w∉V(C_s)∪V(C_t)，w′和w″为w在图G中的两个邻点。显然有

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge 2,\forall a \in V\left( G \right)\\ d\left( {w,w'} \right) = 1,d\left( {w,w''} \right) = 1,d\left( {w',w''} \right) = 2\\ d\left( {a,w} \right) \ge 2,\forall a \in V\left( G \right)\backslash \left\{ {w,w',w''} \right\} \end{array} \right. $

(5)

记G′=G－w+w′w″，G′仍是三圈图，由分析可得

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge \varepsilon '\left( a \right),\varepsilon \left( b \right) \ge \varepsilon '\left( b \right),\forall a,b \in V\left( {G'} \right)\\ d\left( {a,b} \right) \ge d'\left( {a,b} \right),\forall a,b \in V\left( {G'} \right)\\ {\xi ^d}\left( {G'} \right) \ge 4{\left( {n - 1} \right)^2} - 9\left( {n - 1} \right) - 7 = \\ \;\;\;\;\;\;\;\;\;\;4{n^2} - 17n + 6 \end{array} \right. $

(6)

因为式(5)和式(6)成立，所以有

$ \begin{array}{l} {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) \ge 0 + \left( {\varepsilon \left( {w'} \right) + \varepsilon \left( {w''} \right)} \right)d\left( {w',} \right.\\ \left. {w''} \right)\left( {\varepsilon' \left( {w'} \right) + \varepsilon' \left( {w''} \right)} \right)d'\left( {w',w''} \right) + \sum\limits_{a \in \left\{ {w',w''} \right\}} {\left( \varepsilon \right.} \\ \left. {\left( a \right) + \varepsilon \left( w \right)} \right)d\left( {a,w} \right) + \sum\limits_{a \in V\left( {G'} \right)\backslash \left\{ {w',w''} \right\}} {\left( {\varepsilon \left( a \right) + \varepsilon \left( w \right)} \right)} \\ d\left( {a,w} \right) \ge \left( {2 + 2} \right) + 2 \times \left( {2 + 2} \right) + 2 \times \left( {2 + 2} \right) \times \left( {n - } \right.\\ \left. 3 \right) = 8n - 12 \end{array} $

即对于情况2下的三圈图G，有

$ {\xi ^d}\left( G \right) \ge {\xi ^d}\left( {G'} \right) + 8n - 12 > 4{n^2} - 9n - 7 $

引理5由此得证。证毕。

引理6  若G∈T²(n, x, y, z, w)，n≥5，则ξ^d(G)≥4n²－9n－7当且仅当G∈{G₁, G₄, G₅}时等号成立(其中{G₁, G₄, G₅}见图 3)。

证明  显然，n=4时$G \cong {K_4} $(即$G \cong {G_4} $)，ξ^d(G)=ξ^d(K₄)=12，故此处只讨论n≥5的情况。仍对n进行归纳。由引理4可知，当n=5时，ξ^d(G)≥48，当且仅当G∈{G₁, G₄, G₅}时等号成立。假设对任意n－1个顶点的三圈图结论都成立，故只需证明对任意n≥6个顶点的三圈图，结论仍成立。

情况1  若图G中存在悬挂点，不妨取G中任意悬挂点u，顶点u′为u在图G中的唯一邻点。显然有

$ \left\{ \begin{array}{l} \varepsilon \left( u \right) \ge 2,\varepsilon \left( {u'} \right) \ge 1,d\left( {u,u'} \right) = 1\\ \varepsilon \left( a \right) \ge 2,d\left( {a,u} \right) \ge 2,\forall a \in V\left( G \right)\backslash \left\{ {u,u'} \right\} \end{array} \right. $

(7)

记G′=G－u，G′仍是三圈图。由分析可知

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge \varepsilon '\left( a \right),\varepsilon \left( b \right) \ge \varepsilon '\left( b \right),\forall a,b \in V\left( {G'} \right)\\ d\left( {a,b} \right) \ge d'\left( {a,b} \right),\forall a,b \in V\left( {G'} \right)\\ {\xi ^d}\left( {G'} \right) \ge 4{\left( {n - 1} \right)^2} - 9\left( {n - 1} \right) - 7 = \\ \;\;\;\;\;\;\;\;\;\;4{n^2} - 17n + 6 \end{array} \right. $

(8)

因为式(7)和式(8)成立，所以有

$ \begin{array}{l} {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) = \sum\limits_{a,b \in V\left( {G'} \right)} {\left[ {\left( {\varepsilon \left( a \right) + \varepsilon \left( b \right)} \right)} \right.} \\ \left. {d\left( {a,b} \right) - \left( {\varepsilon '\left( a \right) + \varepsilon '\left( b \right)} \right)d'\left( {a,b} \right)} \right] + \left( {\varepsilon \left( {u'} \right) + } \right.\\ \left. {\varepsilon \left( u \right)} \right)d\left( {u,u'} \right) + \sum\limits_{a \in V\left( {G'} \right)\backslash \left\{ {u'} \right\}} {\left( {\varepsilon \left( a \right) + \varepsilon \left( u \right)} \right)d\left( {a,u} \right)} \ge \\ 0 + \left( {1 + 2} \right) \times 1 + \left( {n - 2} \right) \times \left( {2 + 2} \right) \times 2 = 8n - 13 \end{array} $

即对于情况1下的三圈图G，有ξ^d(G)≥ξ^d(G′)+8n－13≥4n²－9n－7，当且仅当G∈{G₁, G₄, G₅}时等号成立。

情况2  若图G中不存在悬挂点，由于n≥6，x+y+z+w－6=n且w≥x≥y≥z，则w≥4。不妨取G中顶点u∈V(P_w)且u∉V(P_x)∪V(P_y)∪V(P_z)，顶点u′和u″为u在图G中的两个邻点。显然有

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge 2,\forall a \in V\left( G \right)\\ d\left( {u,u'} \right) = 1,d\left( {u,u''} \right) = 1,d\left( {u',u''} \right) = 2\\ d\left( {a,u} \right) \ge 2,\forall a \in V\left( G \right)\backslash \left\{ {u,u',u''} \right\} \end{array} \right. $

(9)

记G′=G－u+u′u″，G′仍是三圈图，由分析可知

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge \varepsilon '\left( a \right),\varepsilon \left( b \right) \ge \varepsilon '\left( b \right),\forall a,b \in V\left( {G'} \right)\\ d\left( {a,b} \right) \ge d'\left( {a,b} \right),\forall a,b \in V\left( {G'} \right)\\ {\xi ^d}\left( {G'} \right) \ge 4{n^2} - 17n + 6 \end{array} \right. $

(10)

因为式(9)和式(10)成立，所以有

$ \begin{array}{l} {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) \ge 0 + \left( {\varepsilon \left( {u'} \right),\varepsilon \left( {u''} \right)} \right)d\left( {u',} \right.\\ \left. {u''} \right) - \left( {\varepsilon '\left( {u'} \right),\varepsilon '\left( {u''} \right)} \right)d'\left( {u',u''} \right) + \sum\limits_{a \in \left\{ {u',u''} \right\}} {\left( {\varepsilon \left( a \right) + } \right.} \\ \left. {\varepsilon \left( u \right)} \right)d\left( {a,u} \right) + \sum\limits_{a \in V\left( {G'} \right)\backslash \left\{ {u',u''} \right\}} {\left( {\varepsilon \left( a \right) + \varepsilon \left( u \right)} \right)d\left( {a,} \right.} \\ \left. u \right) \ge \left( {2 + 2} \right) + 2 \times \left( {2 + 2} \right) + 2 \times \left( {2 + 2} \right) \times \left( {n - 3} \right) = \\ 8n - 12 \end{array} $

对于情况2下的三圈图G，有

$ {\xi ^d}\left( G \right) \ge {\xi ^d}\left( {G'} \right) + 8n - 12 > 4{n^2} - 9n - 7 $

引理6由此得证。证毕。

引理7  若G∈T³(n, x, y, z, w)，n≥6，则ξ^d(G)≥4n²－9n－7当且仅当$G \cong {G_2} $时等号成立，其中G₂如图 3所示。

证明  对n进行归纳。由引理4可知，当n=6时，ξ^d(G)≥83当且仅当$G \cong {G_2} $时等号成立。假设对任意n－1个顶点的三圈图，结论都成立，故只需证明对任意n≥7个顶点的三圈图，结论仍成立。

情况1  若图G中存在悬挂点，不妨取G中任意悬挂点u，顶点u′为u在图G中的唯一邻点。显然有

$ \left\{ \begin{array}{l} \varepsilon \left( u \right) \ge 2,\varepsilon \left( {u'} \right) \ge 1,d\left( {u,u'} \right) = 1\\ \varepsilon \left( a \right) \ge 2,d\left( {a,u} \right) \ge 2,\forall a \in V\left( G \right)\backslash \left\{ {u,u'} \right\} \end{array} \right. $

(11)

记G′=G－u，G′仍是三圈图。由分析可知

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge \varepsilon '\left( a \right),\varepsilon \left( b \right) \ge \varepsilon '\left( b \right),\forall a,b \in V\left( {G'} \right)\\ d\left( {a,b} \right) \ge d'\left( {a,b} \right),\forall a,b \in V\left( {G'} \right)\\ {\xi ^d}\left( {G'} \right) \ge 4{\left( {n - 1} \right)^2} - 9\left( {n - 1} \right) - 7 = \\ \;\;\;\;\;\;\;\;\;\;4{n^2} - 17n + 6 \end{array} \right. $

(12)

因为式(11)和式(12)成立，所以有

$ \begin{array}{l} {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) = \sum\limits_{a,b \in V\left( {G'} \right)} {\left[ {\left( {\varepsilon \left( a \right) + \varepsilon \left( b \right)} \right)} \right.} \\ \left. {d\left( {a,b} \right) - \left( {\varepsilon '\left( a \right) + \varepsilon '\left( b \right)} \right)d'\left( {a,b} \right)} \right] + \left( {\varepsilon \left( {u'} \right) + } \right.\\ \left. {\varepsilon \left( u \right)} \right)d\left( {u,u'} \right) + \sum\limits_{a \in V\left( {G'} \right)\backslash \left\{ {u'} \right\}} {\left( {\varepsilon \left( a \right) + \varepsilon \left( u \right)} \right)d\left( {a,u} \right)} \ge \\ 0 + \left( {1 + 2} \right) \times 1 + \left( {n - 2} \right) \times \left( {2 + 2} \right) \times 2 = 8n - 13 \end{array} $

即对于情况1下的三圈图G，有ξ^d(G)≥ξ^d(G′)+8n－13≥4n²－9n－7，当且仅当$G \cong {G_2} $时等号成立。

情况2  若图G中不存在悬挂点，由于n=x+y+z+w－5≥7，x≥y≥z，w≥3，则x=y=z=w=3，或x≥4，或w≥4。

对于n=7，x=y=z=w=3的情况，经过简单计算可以直接得到

$ {\xi ^d}\left( G \right) > {\xi ^d}\left( {{G_2}} \right) = 126 $

对于n>7且x≥4的情况，选取G中顶点u∈V(P_x)且u∉V(C_w)∪V(P_y)∪V(P_z)，顶点u′和u″为u在图G中的两个邻点。显然有

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge 2,\forall a \in V\left( G \right)\\ d\left( {u,u'} \right) = 1,d\left( {u,u''} \right) = 1,d\left( {u',u''} \right) = 2\\ d\left( {a,u} \right) \ge 2,\forall a \in V\left( G \right)\backslash \left\{ {u,u',u''} \right\} \end{array} \right. $

(13)

记G′=G－u+u′u″，G′仍是三圈图。由分析可知

$ \left\{ \begin{array}{l} \varepsilon \left( a \right) \ge \varepsilon '\left( a \right),\varepsilon \left( b \right) \ge \varepsilon '\left( b \right),\forall a,b \in V\left( {G'} \right)\\ d\left( {a,b} \right) \ge d'\left( {a,b} \right),\forall a,b \in V\left( {G'} \right)\\ {\xi ^d}\left( {G'} \right) \ge 4{n^2} - 17n + 6 \end{array} \right. $

(14)

因为式(13)和式(14)成立，所以有

$ \begin{array}{l} {\xi ^d}\left( G \right) - {\xi ^d}\left( {G'} \right) \ge 0 + \left( {\varepsilon \left( {u'} \right),\varepsilon \left( {u''} \right)} \right)d\left( {u',} \right.\\ \left. {u''} \right) - \left( {\varepsilon '\left( {u'} \right),\varepsilon '\left( {u''} \right)} \right)d'\left( {u',u''} \right) + \sum\limits_{a \in \left\{ {u',u''} \right\}} {\left( {\varepsilon \left( a \right) + } \right.} \\ \left. {\varepsilon \left( u \right)} \right)d\left( {a,u} \right) + \sum\limits_{a \in V\left( {G'} \right)\backslash \left\{ {u',u''} \right\}} {\left( {\varepsilon \left( a \right) + \varepsilon \left( u \right)} \right)d\left( {a,} \right.} \\ \left. u \right) \ge \left( {2 + 2} \right) + 2 \times \left( {2 + 2} \right) + 2 \times \left( {2 + 2} \right) \times \left( {n - 3} \right) = \\ 8n - 12 \end{array} $

即ξ^d(G)≥ξ^d(G′)+8n－12>4n²－9n－7成立。

对于n>7且w≥4的情况，选取G中顶点u∈V(C_w)且u∉V(P_x)∪V(P_y)∪V(P_z)，顶点u′和u″为u在图G中的两个邻点。记G′=G－u+u′u″，显然G′仍是三圈图。类似n>7，x≥4的情况，通过证明可以得到ξ^d(G)>4n²－9n－7。

引理7由此得证。证毕。

结合定理1~3及引理5~7，可以得到关于三圈图ξ^d值的最终结论。

定理8  对任意n≥5个顶点的三圈图G，ξ^d(G)≥4n²－9n－7当且仅当G∈{G₁, G₂, G₃, G₄, G₅}时等号成立(其中G₁, G₂, G₃, G₄, G₅见图 3)。

证明  假设G^*是具有最小ξ^d值的三圈图，$\hat G $^*是其基图。结合定理1~3可知，$\hat G $^*的内部不存在割边，且图G^*必然是由(|V(G^*)|－|V($\hat G $^*)|)个孤立顶点连接于$\hat G $ ^*中的同一顶点构成的。此时，G^*要么属于T¹(n, r, s, t)，要么属于T²(n, x, y, z, w)，要么属于T³(n, x, y, z, w)。若

$ {G^ * } \notin \left\{ {{G_1},{G_2},{G_3},{G_4},{G_5}} \right\} $

由引理5~7的证明可知

$ {\xi ^d}\left( {{G^ * }} \right) > 4{n^2} - 9n - 7 $

因此当且仅当G^*∈{G₁, G₂, G₃, G₄, G₅}时ξ^d(G^*)=4n²－9n－7达到最小值。

定理8由此得证。证毕。

3 结束语

本文首先研究了移边变换对离心距离指标的数值影响，然后利用数学归纳计算出了三圈图的离心距离指标的最小值，同时确定了最小值所对应的图的结构。本文的研究方法具有较好的适应性，为研究更一般图的离心距离指标提供了一种新思路。