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

### 引用本文

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.

### 文章历史

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

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

 ${\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)}$

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

 图 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' = 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 - e = {G_1} \cup {G_2},u \in {V_{{G_1}}},v \in {V_{{G_2}}}$

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

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

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

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

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

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

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$

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

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

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

 图 3 具有最小ξd(G)值的三圈图 Fig.3 The tricyclic graphs with minimum ξd(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)

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

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

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

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

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

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

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

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

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

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

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

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

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

 $\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成立。

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

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

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)