直徑為偶數(shù)的二部圖的最小EDS極圖

雷勇,楊?lèi)?ài)民，楊麗英

(1.呂梁學(xué)院 數(shù)學(xué)系,山西 呂梁 033000;2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,山西 太原 030006;3.山西大學(xué) 商務(wù)學(xué)院信息學(xué)院,山西 太原 030031)

直徑為偶數(shù)的二部圖的最小EDS極圖

雷勇1,楊?lèi)?ài)民2，楊麗英3

(1.呂梁學(xué)院 數(shù)學(xué)系,山西 呂梁 033000;2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,山西 太原 030006;3.山西大學(xué) 商務(wù)學(xué)院信息學(xué)院,山西 太原 030031)

距離;直徑;二部圖;EDS

圖的拓?fù)渲笖?shù)能夠很好地刻畫(huà)有機(jī)物分子的生物和物理性質(zhì),因而倍受關(guān)注。 Wiener指數(shù)可能是最早提出的基于距離的一個(gè)拓?fù)渲笖?shù),其定義為

它與分子的許多物理、化學(xué)指標(biāo)有著密切的關(guān)系[3],2002年,Gupta,Singh和Madan[4]提出了另一個(gè)比使用Wiener指數(shù)刻畫(huà)有機(jī)物性質(zhì)更好的指數(shù)──偏心距離和,簡(jiǎn)記為EDS,其定義為

(v).

近年來(lái)關(guān)于圖的EDS指數(shù)有許多重要的結(jié)果[4-13]。 2015年,Li等[1]確定了對(duì)集為q的連通二部圖的EDS下界且給出直徑為奇數(shù)且具有最小EDS的連通二部圖的極圖,并提出三個(gè)重要的開(kāi)放性問(wèn)題,下面是第一個(gè)問(wèn)題。

問(wèn)題 如何確定直徑為偶數(shù)且具有最小EDS的連通二部圖的極圖?

下面我們首先介紹幾個(gè)重要的引理,最后給出這個(gè)問(wèn)題的結(jié)果。

引理1[5]G是一個(gè)n階連通圖,且G≠Kn,則對(duì)于任意邊e?E有ξd(G)>ξd(G+e).

引理2[14]G是一個(gè)直徑為d的n階連通二部圖,設(shè)dG(v0,vd)=d,P=v0v1…vd是一條v0,vd之間的最短路,Vi={v|dG(v0,v)=i},則Vi(i=0,1,…，d)的誘導(dǎo)子圖是空?qǐng)D。

引理3G是一個(gè)直徑為d(≥4)且具有最小EDS的n階連通二部圖,設(shè)dG(v0,vd)=d,P=v0v1…vd是一條v0,vd之間的最短路,Vi={v|dG(v0,v)=i},則Vi∪Vi+1(i=0,1,…,d-1)的誘導(dǎo)子圖是完全二部圖且|Vd|=1.

DG(v)=DG′(v)-2,v∈V0∪…∪Vr-1;

DG(v)=DG′(v)+2,v∈Vr+3∪…∪Vd;

DG(v)=DG′(v),v∈Vr∪Vr+1∪Vr+2;

由EDS的定義可知

引理5G是一個(gè)直徑為偶數(shù)d(≥4)且具有最小EDS的n階連通二部圖,設(shè)dG(v0,vd)=d,P=v0v1…vd是一條v0,vd之間的最短路,Vi={v|dG(v0,v)=i},則

由引理1-5可得到下面的結(jié)論。

定理G是一個(gè)直徑為偶數(shù)d(≥4)且具有最小EDS的n階連通二部圖,則

[1] Li S C,Wu Y Y,Sun L L.On the Minimum Eccentric Distance Sum of Bipartite Graphs with Some Given Parameters[J].JMathAnalAppl,2015,430:1149-1162.DOI:10.1016/j.jmaa.2015. 05.032.

[2] Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:Macmillan London and Elsevier,1976.

[3] Dobrynin A A,Entringer R,Gutman I.Wiener Index of Trees:Theory and Applications[J].ActaApplMath,2001,66:211-249.

[4] Gupta S,Singh M,Madan A K.Eccentric Distance Sum:A Novel Graph Invariant for Predicting Biological and Physical Properties[J].JMathAnalAppl,2002,275:386-401.

[5] Yu G H,Feng L H,Ilic＇ A.On the Eccentric Distance Sum of Trees and Unicyclic Graphs[J].JMathAnalAppl,2011,375:99-107.DOI:10.1016/j.jmaa.2010.08.054.

[6] Hua H B,Zhang S G,Xu K X.Further Results on the Eccentric Distance Sum[J].DiscreteApplMath,2012,160:170-180.DOI:10.1016/j.dam.2011.10.002.

[7] Mao L Y,Cao Q Q,Cui N,etal.On the Extremal Values of the Eccentric Distance Sum of Trees[J].DiscreteApplMath,2015,186:199-206.DOI:10.1016/j.dam.2015.01.042.

[8] Mukungunugwa V,Mukwembi S.On Eccentric Distance Sum and Minimum Degree[J].DiscreteApplMath,2014,175:55-61.DOI:10.1016/j.dam.2014.05.019.

[9] Ilic＇ A,Yu G H,Feng L H.On the Eccentric Distance Sum of Graphs[J].JMathAnalAppl,2011,381:590-600.DOI:10.1016/j.jmaa.2011.02.086.

[10] Geng X Y,Li S C,Zhang M.Extremal Values on the Eccentric Distance Sum of Trees[J].DiscreteApplMath,2013,161:2427-2439.DOI:10.1016/j.dam.2013.05.023.

[11] Li S C,Zhang M,Yu G H,etal.On the Extremal Values of the Eccentric Distance sum of Trees[J].JMathAnalAppl,2012,390:99-112.DOI:10.1016/j.jmaa.2012Z01.022.

[12] 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].JMathAnalAppl,2011,382:364-366.DOI:10.1016/j.jmaa. 2011.04.054.

[13] Azari M,Iranmanesh A.Computing the Eccentric-distance Sum for Graph Operations[J].DiscreteApplMath,2013,161:2827-2840.DOI:10.1016/j.dam.2013.06.003.

[14] Pisanski T,erovik J.Edge-contributions of Some Topological Indices and Arboreality of Molecular Graphs[J].ArsMathContemp,2009,2:49-58.

ExtremalBipartiteGraphsofGivenEvenDiameterHavingMinimalEDS

LEI Yong1，YANG Aimin2，YANG Liying3

(1.DepartmentofMathematic,LvliangUniversity,Lvliang,Shanxi033000,China;2.SchoolofMathematicalSciences,ShanxiUniversity,Taiyuan,Shanxi030006,China;3.SchoolofInformation,BusinessCollegeofShanxiUniversity,Taiyuan,Shanxi030031,China)

distance;diameter;bipartite graph;EDS

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.04.006

2016-12-05；

2017-01-13

呂梁學(xué)院教學(xué)改革項(xiàng)目(JYYBZ201410)；山西省重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(201603D321112)

雷勇(1981-),男,山西興縣人,研究方向:圖論及其應(yīng)用。E-mail:1050506548@qq.com

O157.5

A

0253-2395(2017)04-0717-04