一類強定向的最小平均距離

郝國亮,謝智紅

(東華理工大學(xué) 理學(xué)院,江西 南昌 330013)

?

一類強定向的最小平均距離

郝國亮,謝智紅

(東華理工大學(xué) 理學(xué)院,江西 南昌 330013)

用σG(v)表示圖G中頂點v與G中所有頂點間的距離之和.利用σG(v)指標(biāo)得到了含有割點的2-邊連通圖G的強定向的最小平均距離的若干下界.

2-邊連通圖;強定向;平均距離;割點

MSC 2010：05C20

圖的定向是圖論中一個重要研究方向,具有十分重要的理論意義與現(xiàn)實意義,其應(yīng)用面十分廣泛,涉及到通訊網(wǎng)絡(luò)、計數(shù)化學(xué)、交通控制等很多方面.1939年Robbins[1]在一篇研究單行道交通系統(tǒng)的論文中證明了“任意一個2-邊連通圖都有一個強定向”．強定向的最小平均距離作為圖的一個重要參數(shù),在結(jié)構(gòu)化學(xué)[2]、建筑學(xué)[3]、通訊網(wǎng)絡(luò)等領(lǐng)域都有重要應(yīng)用,在理論研究方面亦有豐碩的研究成果[4].Plesn’ik[5]、Dankelmann等[6]、周濤等[7]、郝國亮[8]研究了強定向的最小平均距離的上下界.Qian等[9]給出了完全二部圖的強定向的最小平均距離的精確值.

目前,大部分文獻只給出了一般2-邊連通圖關(guān)于強定向的最小平均距離的一些上下界，而對于特殊圖類的強定向的最小平均距離的研究相對較少.本文主要利用圖G的σG(v)指標(biāo)研究含有割點的2-邊連通圖的強定向的最小平均距離的下界,這些下界部分改進了已有研究結(jié)果.

1 預(yù)備知識

設(shè)G=(V(G),E(G))表示一個n階無向圖,其中V(G)為頂點集,E(G)為邊集.相應(yīng)地,頂點數(shù)、邊數(shù)分別記為|V(G)|和|E(G)|.對于任意v∈V(G),v的離心率定義為eG(v)=max{dG(v,x):x∈V(G)},其中dG(v,x)是指G中頂點v與頂點x間的距離.用degG(v)表示頂點v在G中的度，無向圖G的σG(v)指標(biāo)定義為

σG(v)=∑x∈V(G)dG(v,x).

若刪掉連通圖G中頂點v所得圖是非連通圖,則稱v是G的割點.不含割點的連通圖稱為塊.若刪掉連通圖G中一條邊所得圖仍是連通圖,則稱G是2-邊連通圖.無向圖G1與G2的并圖G1∪G2是指G的一個子圖,其頂點集為V(G1)∪V(G2),邊集為E(G1)∪E(G2);G1與G2的交圖G1∩G2是指G的一個子圖,其頂點集為V(G1)∩V(G2),邊集為E(G1)∩E(G2).類似地可以定義有向圖D1與D2的并圖D1∪D2與交圖D1∩D2.

設(shè)D=(V(D),A(D))表示一個n階有向圖.若D中存在一條從頂點u到頂點v的有向路,則稱u可達v.給無向圖的每條邊指定一個方向,從而得到一個有向圖,這樣的有向圖稱G為的一個定向.無向圖G的一個定向稱D為強定向,如果D中任意2頂點都可以相互到達.用dD(u,v)表示有向圖D中從頂點u到頂點v的有向距離.有向圖D的總距離σ(D)及平均距離μ(D)分別定義為

σ(D)∑(u,v)∈V(D)×V(D)dD(u,v),μ(D)=σ(D)/n(n-1).

需要注意的是,若不存在從頂點u到頂點v的有向路,則dD(u,v)=∞,此時σ(D)=μ(D)=∞.給定一個2-邊連通圖G,定義G的強定向的最小平均距離為

2 含有割點的2-邊連通圖的強定向的總距離的下界

NG與TEH在文獻[11]中給出了如下結(jié)論：

引理1[11]若是頂點數(shù)為n,邊數(shù)為m的2-邊連通圖G的一個強定向,則

σ(D)≥2n(n-1)-m.

利用引理1,可以得到如下結(jié)論.

定理1 設(shè)G是頂點數(shù)為n,邊數(shù)為m的2-邊連通圖,并設(shè)G=G1∪G2且G1∩G2=ω.若Di是Gi的一個強定向(i=1,2),則,

σ(D)≥2n(n+1)-m-4n1n2+2(n2-1)σG1(ω)+2(n1-1)σG2(ω),

其中D=D1∪D2且ni=|V(Di)|(i=1,2).

證明:令Vi=V(Gi)且mi=|E(Gi)|(i=1,2).顯然n1+nn=n+1且m1+m2=m.注意到,對任意u,v∈V(D)=V(G),dD(u,v)≥dG(u,v).因此由引理1可知,

∑dD(u,v)∈V1×V1(u,v)+∑dD(u,v)∈V2×V2(u,v)+∑u∈V1-{ω},v∈V2-{ω}[dD(u,v)+

dD(v,u)]≥σ(D1)+σ(D2)+2∑u∈V1-{ω},v∈V2-{ω}dG(u,v)=

σ(D1)+σ(D2)+2∑u∈V1-{ω},v∈V2-{ω}[dG(u,ω)+dG(ω,v)]≥

[2n1(n1-1)-m1]+[2n2(n2-1)-m2]+2(n2-1)σG1(ω)+2(n1-1)σG2(ω)=

2n(n+1)-m-4n1n2+2(n2-1)σG1(ω)+2(n1-1)σG2(ω).

3 含有割點的2-邊連通圖G關(guān)于min(G)的下界

本節(jié)主要利用定理1給出含有割點的2-邊連通圖的強定向的最小平均距離的幾個下界.

命題1 設(shè)G是頂點數(shù)為n的塊,并設(shè)v是G的任意一個頂點,則

σG(v)≥n-1+[eG(v)-1]2.

證明:設(shè)eG(v)=d,并設(shè)pi=|{x∈V(G):dG(v,x)=i}|(i=1,2,…,d).因為G是塊,所以pi≥2(i=1,2,…,d-1)且pd≥1.因此

利用定理1及命題1,可以得到如下結(jié)論.

定理2 設(shè)G是頂點數(shù)為n,邊數(shù)為m的2-邊連通圖.若G=G1∪G2且G1∩G2=ω,其中Gi為塊(i=1,2),則

其中d=min{eGi(ω):i=1,2}.

證明:設(shè)Vi=V(Gi),并設(shè)ni=|Vi|(i=1,2).顯然n1+n2=n+1.令Di是Gi的一個強定向(i=1,2).易見D=D1∪D2是G的一個強定向.因此由定理1及命題1知

σ(D)≥2n(n+1)-m-4n1n2+2(n2-1)σG1(ω)+2(n1-1)σG2(ω)≥

2n(n+1)-m-4n1n2+2(n2-1)[n1-1+(eG1(ω)-1)2]+2(n1-1)[n2-1+(eG2(ω)-1)2]≥

2n(n+1)-m-4n1n2+2(n2-1)[n1-1+(d-1)2]+2(n1-1)[n2-1+(d-1)2]=

2n(n-1)-m+2(d-1)2(n-1).

下面將部分改進定理2中的下界,為此先給出如下命題.

命題2 設(shè)G是頂點數(shù)為n的塊,并設(shè)v是G的任意一個頂點,則

σG(v)≥2(n-1)-degG(v)+[eG(v)-2]2.

證明:設(shè)eG(v)=d,并設(shè)pi=|{x∈V(G):dG(v,x)=i}|(i=1,2,…,d).因為G是塊,所以pi≥2(i=1,2,…,d-1),pd≥1.因此,要使σG(v)=1·p1+2·p2+…+d·pd最小,則只需要p3=p4=…=pd-1=2與pd=1,此時

于是

利用定理1及命題2,可以得到如下結(jié)論.

定理3 設(shè)G是頂點數(shù)為n,邊數(shù)為m的2-邊連通圖.若G=G1∪G2且G1∩G2=ω,其中Gi為塊(i=1,2),則μmin(G)≥2-mn(n-1)+4(n1n2-n)n(n-1)+2[(d2-2)2-d1]n,其中ni=|V(Gi)|(i=1,2),d1=max{degGi(ω):i=1,2},d2=min{eGi(ω):i=1,2}.

證明:設(shè)Di是Gi的一個強定向(i=1,2)，則顯然D=D1∪D2是G的一個強定向.注意到n1+n2=n+1.因此,由定理1及命題2可知

設(shè)G=G1∪G2且G1∩G2=ω.若G1和G2中至少有一個不是塊,則下面將給出μmin(G)的一個下界,為此先給出如下命題.

命題3 設(shè)G是頂點數(shù)為n的2-邊連通圖,并設(shè)v是G的任意一個頂點,則

σG(v)≥2(n-1)-degG(v).

證明:設(shè)eG(v)=d,并設(shè)pi=|{x∈V(G):dG(v,x)=i}|(i=1,2,…,d).顯然

σG(v) =1·p1+2·p2+…+d·pd≥p1+2(p2+p3+…+pd)≥

degG(v)+2[n-1-degG(v)]≥2(n-1)-degG(v).

利用定理1及命題3,可以得到如下結(jié)論.

定理4 設(shè)G是頂點數(shù)為n,邊數(shù)為m的2-邊連通圖.若G=G1∩G2且G1∩G2=ω,則μmin(G)≥2-mn(n-1)+4(n1n2-n)n(n-1)-2dn,其中ni=|V(Gi)|(i=1,2),d=max{degGi(ω):i=1,2}.

證明:設(shè)Di是Gi的一個強定向(i=1,2),則顯然D=D1∪D2是G的一個強定向.注意到n1+n2=n+1.因此,由定理1及命題3可知

σ(D)≥2n(n+1)-m-4n1n2+2(n2-1)σG1(ω)+2(n1-1)σG2(ω)≥

2n(n+1)-m-4n1n2+2(n2-1)[2(n1-1)-degG1(ω)]+2(n1-1)[2(n2-1)-degG2(ω)]=

2n(n+1)-m-4n1n2+8(n1-1)(n2-1)-2(n2-1)degG1(ω)-2(n1-1)degG2(ω)≥

2n(n+1)-m-4n1n2+8(n1-1)(n2-1)-2(n1+n2-2)d=

2n(n-1)-m+4(n1n2-n)-2(n-1)d.

[1]ROBBINSHE.Atheoremongraphswithanapplicationtoaproblemoftrafficcontrol[J].AmMathMon,1939,46:281-283.

[2]DOYLEJK.Meandistanceinagraph[J].DiscreteMath,1977,17:147-154.

[3]CHUNGFRK.Theaveragedistanceandtheindependencenumber[J].JournalofGraphTheory,1988,12:229-235.

[4]KOHKM,TAYEG.Optimalorientationsofgraphsanddigraphs:asurvey[J].GraphsandCombinatorics,2002,18:745-756.

[5]PLESN’IKJ.Onthesumofalldistancesinagraphordigraph[J].GraphTheory,1984,8:1-21.

[6]DANKELMANNP,OELLERMANNOR,WUJL.Minimumaveragedistanceofstrongorientationsofgraphs[J].DiscreteAppliedMathematics,2004,143:204-212.

[7] 周濤,徐俊明,劉雋.圖直徑與平均距離的極值問題研究[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2004,34(4):410-413.ZHOUT,XUJM,LIUJ.Extremalproblemondiameterandaveragedistanceofgraphs[J].JournalofUniversityofScienceandTechnologyofChina,2004,34(4):410-413.

[8] 郝國亮.強定向圖平均距離的界[J].延邊大學(xué)學(xué)報(自然科學(xué)版),2008,34(4):238-239.HAOGL.Boundoftheaveragedistanceofthestrongorientations[J].JournalofYanbianUniversity(NaturalScienceEdition),2008,34(4):238-239.

[9]QIANJG,ENGELK,XUWI.AgeneralizationofSperner’stheoremandanapplicationtographorientations[J].DiscreteAppliedMath,2009,157:2170-2176.

[10]BONDYJA,MURTYUSR.GraphTheory[M].NewYork：Springer, 2008.

[11]NGCP,TEHHH.Onfinitegraphsofdiameter2[J].NantaMath,1966，67(1):72-75.

(責(zé)任編輯：王蘭英)

Minimum average distance of a class of strong orientations

HAO Guoliang,XIE Zhihong

(College of Science,East China University of Technology,Nanchang 330013,China)

LetσG(v)denotes the sum of the distance between the vertex of and all of the vertices ofG.By making use of theσG(v) index,some lower bounds on the minimum average distance of all strong orientations of a 2-edge connected graphGwith at least a cut vertex were established.

2-edge connected graph；strong orientation；average distance；cut vertex

10.3969/j.issn.1000-1565.2017.02.001

2016-07-21

國家自然科學(xué)基金資助項目(11471273);江西省教育廳科學(xué)技術(shù)研究項目(GJJ150561);東華理工大學(xué)博士科研啟動基金資助項目(DHBK2015319；DHBK2015320)

郝國亮(1980—),男,山東肥城人,東華理工大學(xué)講師,博士,主要從事組合圖論方向研究. E-mail:guoliang-hao@163.com

O157.5

A

1000-1565(2017)02-0113-04