圖的給定匹配數(shù)的離心率距離和

（天津科技大學(xué)理學(xué)院，天津 300457）

（天津科技大學(xué)理學(xué)院，天津 300457）

針對(duì)可預(yù)測(cè)生物和物理性質(zhì)的圖的不變量——離心率距離和，采用Tutte-Berge公式及圖的轉(zhuǎn)化方法，給出了圖的給定匹配數(shù)的離心率距離和的緊下界，且完全確定了其極值圖.

離心率距離和；匹配數(shù)；極值圖

Wiener指標(biāo)定義為對(duì)所有無(wú)序頂點(diǎn)對(duì)之間距離的求和［1］：

它被認(rèn)為是與分子化合物的許多物理和化學(xué)指標(biāo)高度相關(guān)的最有用的拓?fù)渲笜?biāo)之一.

1997年，Sharma等［2］引進(jìn)了 1個(gè)基于距離的分子結(jié)構(gòu)描述量，被稱為離心率連通性指標(biāo)（ECI），定義為ξc（G）指標(biāo)被成功應(yīng)用在不同性質(zhì)的生物活性的數(shù)學(xué)模型上［2］.

2002年，Gupta等［3］提出了1個(gè)新奇的預(yù)測(cè)生物和物理性質(zhì)的圖的不變量——離心率距離和.他們證明了對(duì)一些構(gòu)造活動(dòng)和定量結(jié)構(gòu)性質(zhì)的研究，使用離心率距離和所得的值比使用 Wiener指標(biāo)要好.離心率距離和（EDS）定義為

如果圖的1個(gè)連通分支含有偶（或奇）數(shù)個(gè)頂點(diǎn)，那么稱這個(gè)連通分支是偶（或奇）的.令G是1個(gè)有n個(gè)頂點(diǎn)的圖，且 o（G）表示G中奇分支的個(gè)數(shù).由Tutte-Berge公式［4］，有

圖G和H的頂點(diǎn)不交的并，記作G H∪ .令G H∨ 表示在G H∪ 中通過(guò)從G中的頂點(diǎn)向H中的頂點(diǎn)連接所有可能的邊而所得的圖，即

因?yàn)樵趫D中添加新邊會(huì)降低一些距離，所以有：

Feng等［5］研究了在階為n且匹配數(shù)是β的所有圖中有最大譜半徑的極值圖.Zhou等［6］確定了連通圖的與頂點(diǎn)數(shù)及匹配數(shù)相關(guān)的最小 Kirchhoff指標(biāo).2010年，F(xiàn)eng等［7］給出了圖的給定匹配數(shù)的Zagreb指標(biāo)、Harary指標(biāo)和超 Wiener指標(biāo)的緊上（下）界，且確定了它們的極值圖.2011年，Yu等［8］研究了給定圍長(zhǎng)的單圈圖的離心率距離和，且刻畫(huà)了最小和次最小離心率距離和的極值圖.此外，他們還刻畫(huà)了給定直徑的一類樹(shù)的最小和次最小離心率距離和的極值樹(shù).但是，對(duì)于圖的給定匹配數(shù)的離心率距離和的極值圖研究目前還沒(méi)有結(jié)果.

本文解決了這個(gè)問(wèn)題，給出了給定匹配數(shù)的離心率距離和的緊上界，且完全確定了其極值圖.對(duì)離心率距離和的進(jìn)一步研究具有一定的理論意義.文中未加述及的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)［9］.

證明：令 G0是所有階為n且匹配數(shù)為β的連通圖中離心率距離和最小的圖.由式（1）的 Tutte-Berge公式，存在頂點(diǎn)集 X0? V（G0）使得為 方 便 起見(jiàn)，令X0=s且 o（G0- X0）=t，則n - 2β=t-s .

以下假設(shè) s≥1，從而 t≥1.令 G1，G2，… ，Gt是G0- X0的所有奇分支.若 G0- X0有一個(gè)偶分支，則在 G0中通過(guò)添加一條連接 G0- X0的偶分支的一個(gè)頂點(diǎn)和奇分支的一個(gè)頂點(diǎn)的邊，得到一個(gè)圖，滿足n -2β）≥o-X0）- X0= o（G0-X0）-X0.從而有β）= β，且由引理 1，G?的離心率距離和比 G0小，矛盾.因此，G0- X0不含有任何偶分支.類似地，G1，G2，… ，Gt及由 X0導(dǎo)出的子圖都是完全圖，且G1，G2，… ，Gt中的任一頂點(diǎn)鄰接于 X0的每一個(gè)頂點(diǎn).令ni= V（Gi），i = 1，2，… ，t ，則

注意到，0G的直徑是2，從而

從而

因此，式（2）可改寫(xiě)為

由于 β≥2，有 g（1）- g（β）=1-5 n - 10β2+9β + 5nβ .令b是二次方程 - 10β2+ （5 n + 9）β +1-5 n=0的一個(gè)較大的根，則

因此，若 β≤ b，則 g （1）≤ g（β）；而當(dāng) β≥ b，則g （β）≤ g（1）.證畢.

［1］ Wiener H. Structural determination of paraffin boiling point［J］. Journal of the American Chemical Society，1947，69（1）：17-20.

［2］ Sharma V，Goswami R，Madan A K. Eccentric connectivity index：A novel highly discriminating topological descriptor for structure property and structure activity studies［J］. Journal of Chemical Information and Computer Science，1997，37（2）：273-282.

［3］ Gupta S，Singh M，Madan A K. Eccentric distance sum：A novel graph invariant for predicting biological and physical properties［J］. Journal of Mathmatical Analysis and Applications，2002，275（1）：386-401.

［4］ Lovász L，Plummer M D. Matching Theory［M］. Budapest：Akadémiai Kiadó，1986.

［5］ Feng L H，Yu G H，Zhang X D. Spectral radius of graphs with given matching number［J］. Linear Algebra and its Applications，2007，422（1）：133-138.

［6］ Zhou B，Trinajstic N. The Kirchhoff index and the matching number［J］. International Journal of Quantum Chemistry，2009，109（13）：2978-2981.

［7］ Feng L H，Ilic A. Zagreb，Harary and hyper-Wiener indices of graphs with given matching number［J］. Applied Mathematics Letters，2010，23（8）：943-948.

［8］ Yu G H，F(xiàn)eng L H，Ilic A. On the eccentric distance sum of trees and unicyclic graphs［J］. Journal of Mathmatical Analysis and Applications，2011，375（1）：99-107.

［9］ Bondy J A，Murty U S R. Graph Theory with Applications［M］. London：Macmillan Press Ltd，1976.

圖的給定匹配數(shù)的離心率距離和

安明強(qiáng)，孫明晶，劉寅立，孟祥波

Eccentric Distance Sum of Graphs with a Given Matching Number

AN Mingqiang，SUN Mingjing，LIU Yinli，MENG Xiangbo
（College of Science，Tianjin University of Science & Technology，Tianjin 300457，China）

Aimed at a novel graph invariant for predicting biological and physical properties named eccentric distance sum，by using the Tutte-Berge formula and the method of graph transformation，sharp lower bound for the eccentric distance sum of graphs with a given matching number，and the extremal graphs were successully determined.

eccentric distance sum；matching number；extremal graphs

O157.5 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1672-6510（2015）02-0075-03

10.13364/j.issn.1672-6510.20140072

2014-05-12；

2014-08-29

國(guó)家自然科學(xué)基金資助項(xiàng)目（11001197）

安明強(qiáng)（1982—），男，甘肅天水人，講師，anmq@tust.edu.cn.

常濤

【科研成果簡(jiǎn)介】