文章快速检索     高级检索
  北京化工大学学报(自然科学版)  2018, Vol. 45 Issue (1): 109-114  DOI: 10.13543/j.bhxbzr.2018.01.018
0

文章浏览量:[]

引用本文  

费军旗, 涂建华. 三圈图的最小离心距离指标[J]. 北京化工大学学报(自然科学版), 2018, 45(1): 109-114. DOI: 10.13543/j.bhxbzr.2018.01.018.
FEI JunQi, TU JianHua. Tricyclic graphs with a minimum eccentric distance sum[J]. Journal of Beijing University of Chemical Technology (Natural Science), 2018, 45(1): 109-114. DOI: 10.13543/j.bhxbzr.2018.01.018.

基金项目

国家自然科学基金(11201021)

第一作者

费军旗, 男, 1993年生, 硕士生

通讯联系人

涂建华, E-mail:tujh81@163.com

文章历史

收稿日期:2017-05-09
三圈图的最小离心距离指标
费军旗 , 涂建华     
北京化工大学 理学院, 北京 100029
摘要:为进一步研究离心距离指标(EDS)数学性质,通过研究3种移边变换对离心距离指标的影响,利用移边变换和数学归纳得出了三圈图离心距离指标的最小值及其对应图的结构。本文方法为研究更一般图的离心距离指标提供了一种简单有效的思路。
关键词图论不变量    离心距离    三圈图    
Tricyclic graphs with a minimum eccentric distance sum
FEI JunQi , TU JianHua     
Faculty of Science, Beijing University of Chemical Technology, Beijing 100029, China
Abstract: The eccentric distance sum (EDS) has been widely used in the fields of chemistry and biology. In order to study its mathematical properties further, a new method has been used in this paper. Firstly, three transformations of edge-grafting on the eccentricity distance sum of a connected graph were studied. Then by using these transformations and induction, we obtained the minimum eccentric distance sum among all tricyclic graphs with order n, and also characterized the structure of the corresponding tricyclic graphs. The results demonstrate that our method is simple and effective, and offers a new way of studying the eccentric distance sum of general graphs.
Key words: graph invariant    eccentric distance sum    tricyclic graphs    
引言

图论不变量是一些特殊的拓扑指标,常被用来描述某些化学分子结构图的基础性质。基于顶点间距离的不变量如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)} $

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

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

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

图 1 3种移边变换 Fig.1 Three edge-grafting transformations
$ 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个悬挂点(u1, u2, …, up),顶点v(不同于顶点u)在图G中具有q个悬挂点(v1, v2, …, vq)。则第二变换GG′和GG″分别为

$ 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)中的GG′变换记为第三变换。

本文通过计算验证了这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′中任意两点xy,假设ε(x):=εG(x)或ε′(x):=εG(x),d(x, y):=dG(x, y)或d′(x, y):=dG(x, y)

证明(定理1)

对于图 1中的图GG′,假设|V(H)|>1,W={v1, v2, …, vp},可以得到

$ \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 $

由此可知ξ2>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的唯一不包含悬挂点的三圈子图。一般性地,用Cn表示n个顶点构成的圈,用Pn表示n个顶点构成的路。

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

1) T1(n, r, s, t)={G},其中rst分别表示图$\hat G $中的3个圈CrCsCtrst,且CrCsCt彼此之间在图$\hat G $中至多有1个公共顶点;

2) T2(n, x, y, z, w)={G},其中x, y, z分别表示$\hat G $中连通顶点pq的3条内部不交的路PxPyPzw表示$\hat G $中连通顶点gh的路Pwwxyz,且$\left\{ {g, h} \right\} \subset \bigcup\limits_{i = x, y, z} {V\left( {{P_i}} \right)} $

3) T3(n, x, y, z, w)={G},其中x, y, z分别表示$\hat G $中连通顶点pq的3条内部不交的路PxPyPz(xyz),w表示$\hat G $中悬挂于顶点g的圈Cw(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  若三圈图GT1(7, r, s, t),则ξd(G)≥126;若三圈图GT2(5, x, y, z, w),则ξd(G)≥48;若三圈图GT3(6, x, y, z, w),则ξd(G)≥83。

证明  显然,如图 2所示,若三圈图GT1(7, r, s, t),则

图 2 n=5, 6, 7时的某些特殊三圈图 Fig.2 Some special tricyclic graphs with order n=5, 6, 7
$ G \in \left\{ {{T^{1\left( 1 \right)}},{T^{1\left( 2 \right)}}} \right\} $

若三圈图GT2(5, x, y, z, w),则

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

若三圈图GT3(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  若三圈图GT1(n, r, s, t),n≥7,则ξd(G)≥4n2-9n-7,当且仅当$G \cong {G_3} $时等号成立(其中G3图 3所示)。

图 3 具有最小ξd(G)值的三圈图 Fig.3 The tricyclic graphs with minimum ξd(G)

证明  对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′=GwG′仍是三圈图,由分析可知

$ \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≥4n2-9n-7,当且仅当$G \cong {G_3} $时等号成立。

情况2  若图G中不存在悬挂点,由于n≥8,r+s+t-2=n,且rst,则有r≥4。不妨取G中顶点wV(Cr)且wV(Cs)∪V(Ct),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′=Gw+ww″,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  若GT2(n, x, y, z, w),n≥5,则ξd(G)≥4n2-9n-7当且仅当G∈{G1, G4, G5}时等号成立(其中{G1, G4, G5}见图 3)。

证明  显然,n=4时$G \cong {K_4} $(即$G \cong {G_4} $),ξd(G)=ξd(K4)=12,故此处只讨论n≥5的情况。仍对n进行归纳。由引理4可知,当n=5时,ξd(G)≥48,当且仅当G∈{G1, G4, G5}时等号成立。假设对任意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′=GuG′仍是三圈图。由分析可知

$ \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≥4n2-9n-7,当且仅当G∈{G1, G4, G5}时等号成立。

情况2  若图G中不存在悬挂点,由于n≥6,x+y+z+w-6=nwxyz,则w≥4。不妨取G中顶点uV(Pw)且uV(Px)∪V(Py)∪V(Pz),顶点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′=Gu+uu″,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  若GT3(n, x, y, z, w),n≥6,则ξd(G)≥4n2-9n-7当且仅当$G \cong {G_2} $时等号成立,其中G2图 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′=GuG′仍是三圈图。由分析可知

$ \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≥4n2-9n-7,当且仅当$G \cong {G_2} $时等号成立。

情况2  若图G中不存在悬挂点,由于n=x+y+z+w-5≥7,xyzw≥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中顶点uV(Px)且uV(Cw)∪V(Py)∪V(Pz),顶点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′=Gu+uu″,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>4n2-9n-7成立。

对于n>7且w≥4的情况,选取G中顶点uV(Cw)且uV(Px)∪V(Py)∪V(Pz),顶点u′和u″为u在图G中的两个邻点。记G′=Gu+uu″,显然G′仍是三圈图。类似n>7,x≥4的情况,通过证明可以得到ξd(G)>4n2-9n-7。

引理7由此得证。证毕。

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

定理8  对任意n≥5个顶点的三圈图Gξd(G)≥4n2-9n-7当且仅当G∈{G1, G2, G3, G4, G5}时等号成立(其中G1, G2, G3, G4, G5图 3)。

证明  假设G*是具有最小ξd值的三圈图,$\hat G $*是其基图。结合定理1~3可知,$\hat G $*的内部不存在割边,且图G*必然是由(|V(G*)|-|V($\hat G $*)|)个孤立顶点连接于$\hat G $ *中的同一顶点构成的。此时,G*要么属于T1(n, r, s, t),要么属于T2(n, x, y, z, w),要么属于T3(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*∈{G1, G2, G3, G4, G5}时ξd(G*)=4n2-9n-7达到最小值。

定理8由此得证。证毕。

3 结束语

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

参考文献
[1] Wiener H, Structural determination of paraffin boiling points[J]. Journal of the American Chemical Society, 1947, 69(1): 17-20. DOI:10.1021/ja01193a005 (in Chinese)
[2] Dobrynin A A, Entringer R, Gutman I, Wiener index of trees:theory and applications[J]. Acta Applicandae Mathematicae, 2001, 66(3): 211-249. DOI:10.1023/A:1010767517079 (in Chinese)
[3] 杜永军, 吴建春. 单圈图Wiener指标的极值[J]. 兰州理工大学学报, 2013, 39(2): 163-165.
Du Y J, Wu J C, Extremum of Wiener indices on unicyclic graphs[J]. Journal of Lanzhou University of Technology, 2013, 39(2): 163-165. (in Chinese)
[4] Dobrynin A A, Kochetova A A, Degree distance of a graph:a degree analogue of the Wiener index[J]. Journal of Chemical Information & Modeling, 1994, 34(5): 1082-1086. (in Chinese)
[5] Gutman I, A property of the Wiener number and its modifications[J]. Indian Journal of Chemistry, 1997, 36(2): 128-132. (in Chinese)
[6] 何秀萍. 具有最小度距离的双圈图[J]. 数学研究, 2008, 41(4): 434-438.
He X P, The bicyclic graphs with minimal degree distance[J]. Journal of Mathematical Study, 2008, 41(4): 434-438. (in Chinese)
[7] Gupta S, Singh M, Madan A K, Eccentric distance sum:a novel graph invariant for predicting biological and physical properties[J]. Journal of Mathematical Analysis & Applications, 2002, 275(1): 386-401. (in Chinese)
[8] Yu G H, Feng L H, Ilić A, On the eccentric distance sum of trees and unicyclic graphs[J]. Journal of Mathematical Analysis & Applications, 2011, 375(1): 99-107.
[9] Ilić A, Yu G H, Feng L H, On the eccentric distance sum of graphs[J]. Journal of Mathematical Analysis & Applications, 2011, 381(2): 590-600.
[10] Hua H B, Xu K X, Wen S, A short and unified proof of Yu et al.'s two results on the eccentric distance sum[J]. Journal of Mathematical Analysis & Applications, 2011, 382(1): 364-366.
[11] Li S C, Wu Y Y, On the extreme eccentric distance sum of graphs with some given parameters[J]. Discrete Applied Mathematics, 2016, 206: 90-99. DOI:10.1016/j.dam.2016.01.027 (in Chinese)
[12] Li S C, Wei W, Some edge-grafting transformations on the eccentricity resistance-distance sum and their applications[J]. Discrete Applied Mathematics, 2016, 211: 130-142. DOI:10.1016/j.dam.2016.04.014 (in Chinese)