圖的ABC指標與直徑

武 琳，胡玉梅

(天津大學(xué)理學(xué)院，天津 300350)

?

圖的ABC指標與直徑

武 琳，胡玉梅

(天津大學(xué)理學(xué)院，天津 300350)

為了更好地研究拓撲指標在物理化學(xué)領(lǐng)域的良好性質(zhì)，考慮基于度和基于距離的指標之間的關(guān)系問題，在直徑這一作為距離的不變量的基礎(chǔ)上，研究了圖的ABC指標和直徑的關(guān)系。根據(jù)相關(guān)引理，推導(dǎo)出了樹和單圈圖的ABC指標與直徑的關(guān)系，得出了ABC指標和直徑差值的緊的下界。

代數(shù)拓撲；ABC指標；直徑；樹；單圈圖；極值

拓撲指標在物理化學(xué)領(lǐng)域有著廣泛的應(yīng)用價值和深遠的研究意義[1-9]。隨著圖論理論的不斷發(fā)展和完善，拓撲指標主要分為2類：基于度的指標和基于距離的指標。ABC指標是一個基于度的拓撲指標，它由ESTRADA等[10]提出，相關(guān)性質(zhì)的研究見文獻[11—17],圖G的ABC指標的定義式為

1 樹的ABC指標與直徑

引理1 設(shè)x1x2是圖G中的懸掛邊，則ABC(G)-ABC(G-x1x2)>0。

證明

ABC(G)-ABC(G-x1x2)=

假設(shè)T不是路，故T至少有3個懸掛邊。若P=v0v1…vD是T的直徑路，則V(P)=D+1,E(P)=D,D(P)=D(T)=D。令u1,u2,…,um是不在直徑路P上的懸掛點，則有：

2 單圈圖的ABC指標與直徑

引理2 設(shè)G是一個不同構(gòu)于Cn的單圈圖，n≥7，n1≤(n-3)，v是G的直徑路P上的葉子點，u是v的鄰點。若N(u)中僅有一個頂點的度數(shù)不小于2，則有：

當D(G-v)=D(G)時，ABC(G)-ABC(G-v)>0；

證明 令N(u)-{v}={x1,x2,…,xd(u)-1}，不妨設(shè)x1是度數(shù)不小于2的頂點。

當D(G-v)=D(G)時，顯然有d(u)≥3，此時，

ABC(G)-ABC(G-v)=

當D(G-v)=D(G)-1時，顯然有d(u)=2。設(shè)w是u的鄰點，d(w)≥2，則有：

證明 情況1N(u)僅有一個頂點的度至少是2，對n用數(shù)學(xué)歸納法，

情況2N(u)中有2個頂點的度數(shù)不小于2，

當D(G-v)=D(G)時，

若G僅有1個葉子點v，與D(G-v)=D(G)矛盾；

若G有多于2個葉子點，依次刪除不在直徑路上的葉子點，得到圖G′，則

[1] RANDIC M. Characterization of molecular branching[J]. Journal of the American Chemical Society, 1975, 97(23): 6609-6615.

[2] ROUVRAY H D. Predicting chemistry from topology[J]. Scientific American, 1986, 255:40-47.

[3] ROUVRAY H D. The modeling of chemical phenomena using topological indices[J]. Journal of Computational Chemistry, 1987, 8(4):470-480.

[4] WIENER H. Structural determination of paraffin boiling points[J]. Journal of the American Chemical Society, 1947, 69(1):17-20.

[5] ZHOU B, TRINAJSTIC N. On a novel connectivity index[J]. Journal of Mathematical Chemistry, 2009, 46(4):1252-1270.

[6] ZHOU B, TRINAJSTIC N. On general sum-connectivity index[J]. Journal of Mathematical Chemistry, 2010, 47(1):210-218.

[7] GAO J, LU M. On the randic index of unicyclic graphs[J]. Match Communications in Mathematical & in Computer Chemistry, 2005, 53(2):377-384.

[8] GUTMAN I, POTGIETER H J. Wiener index and intermolecular forces[J]. South African Journal of Science, 1996, 92(3):47-48.

[9] BOLLOBAAS B, ERDOS P. Graphs of extremal weights[J]. Ars Combinatoria,1998,50:225-233.

[10]ESTRADA E, TORRES L, RODRIGUEZ L, et al . An atom-bond connectivity index: Modelling the enthalpy of formation of alkanes[J]. Indian Journal of Chemistry, 1998, 37(10):849-855.

[11]ESTRADA E. Atom-bond connectivity and the energetic of branched alkanes[J]. Chemical Physics Letters, 2008, 463(4/5/6):422-425.

[12]DAS C K. Atom-bond connectivity index of graphs[J]. Discrete Applied Mathematics, 2010, 158(11):1181-1188.

[13]FURTULA B, GRAOVAC A, VUKICEVIC D.Atom-bond connectivity index of trees[J]. Discrete Applied Mathematics, 2009, 175: 2828-2835.

[14]GUTMAN I, FURTULA B. Trees with smallest atom-bond connectivity index[J]. Match Communications in Mathematical & in Computer Chemistry, 2012, 68(1):131-136.

[15]GUTMAN I, FURTULA B, IVANOVIC M. Notes on trees with minimal atom-bond connectivity index[J]. Match Communications in Mathematical & in Computer Chemistry, 2012, 67(3):467-482.

[16]HOSSEINI A S, AHMADI B M, GUTMAN I. Kragujevac trees with minimal atom-bond connectivity index[J]. MATCH Commun Math Comput Chem, 2014, 71(20): 5-20.

[17]ZHOU B, XING R. On atom-bond connectivity index[J]. Zeitschrift Fur Naturforschung A, 2011, 66(1/2):61-66.

[18]CHEN L, LI X, LIU M, et al. On a relation between szeged and wiener indices of bipartite graphs[J]. Transactions on Combinatorics, 2012, 1(4):43-49.

[19]HOROLDAGVA B,DAS K C. On comparing Zagreb indices of graphs[J]. Hacettepe University Bulletin of Natural Sciences and Engineering,2012,41(4):223-230.

[20]HOROLDAGVA B, GUTMAN I. On some vertex-degree-based graph invariants[J]. Match Communications in Mathematical & in Computer Chemistry, 2011, 65(3):723-730.

[21]LIU Jianxi. On harmonic index and diameter of graphs[J]. Journal of Appied Mathematics and Physics, 2013,1(3):5-6.

Atom-bond connectivity index and diameter of graphs

WU Lin, HU Yumei

(School of Science, Tianjin University, Tianjin 300350, China)

For further study of the numerous nice properties of topological indices in physical and chemical fields, it is worth considering the relation between a degree-based index and a distance-based index. With the fact that diameter is an invariant based on distance, the relations between atom-bond connectivity index, diameter in trees and unicyclic graphs are studied. Based on relative lemma, the relation between atom-bond connectivity index and diameter in tree and unicyclic graphs is investigated, then the sharp lower bounds of the difference of index and diameter are given.

algebraic topology；ABCindex； diameter； tree； unicyclic graph； extreme value

1008-1542(2016)06-0552-04

10.7535/hbkd.2016yx06005

2016-03-29；

2016-09-29；責(zé)任編輯：張 軍

國家自然科學(xué)基金(11001196)

武 琳(1992-)，女，天津人，碩士研究生，主要從事圖論與組合最優(yōu)化方面的研究。

胡玉梅副教授。E-mail：huyumei@tju.edu.cn

O157 MSC(2010)主題分類：55-04

A

武 琳，胡玉梅.圖的ABC指標與直徑[J].河北科技大學(xué)學(xué)報,2016,37(6):552-555. WU Lin, HU Yumei .Atom-bond connectivity index and diameter of graphs[J].Journal of Hebei University of Science and Technology,2016,37(6):552-555.