武 琳，胡玉梅

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

?

圖的ABC指標(biāo)與直徑

武 琳，胡玉梅

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

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

代數(shù)拓?fù)?；ABC指標(biāo)；直徑；樹；單圈圖；極值

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

1 樹的ABC指標(biāo)與直徑

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

證明

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

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

2 單圈圖的ABC指標(biāo)與直徑

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

當(dāng)D(G-v)=D(G)時(shí)，ABC(G)-ABC(G-v)>0；

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

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

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

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

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

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

當(dāng)D(G-v)=D(G)時(shí)，

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

若G有多于2個(gè)葉子點(diǎn)，依次刪除不在直徑路上的葉子點(diǎn)，得到圖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指標(biāo)與直徑[J].河北科技大學(xué)學(xué)報(bào),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.