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

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

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

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

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

Wiener指標(biāo)定義為對(duì)所有無序頂點(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∪ 中通過從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］研究了給定圍長的單圈圖的離心率距離和，且刻畫了最小和次最小離心率距離和的極值圖.此外，他們還刻畫了給定直徑的一類樹的最小和次最小離心率距離和的極值樹.但是，對(duì)于圖的給定匹配數(shù)的離心率距離和的極值圖研究目前還沒有結(jié)果.

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

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

以下假設(shè) s≥1，從而 t≥1.令 G1，G2，… ，Gt是G0- X0的所有奇分支.若 G0- X0有一個(gè)偶分支，則在 G0中通過添加一條連接 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）可改寫為

由于 β≥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

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

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

常濤

【科研成果簡介】