一类强定向的最小平均距离

郝国亮,谢智红

(东华理工大学 理学院,江西 南昌 330013)



一类强定向的最小平均距离

郝国亮,谢智红

(东华理工大学 理学院,江西 南昌 330013)

用σG(v)表示图G中顶点v与G中所有顶点间的距离之和.利用σG(v)指标得到了含有割点的2-边连通图G的强定向的最小平均距离的若干下界.

2-边连通图;强定向;平均距离;割点

MSC 2010：05C20

图的定向是图论中一个重要研究方向,具有十分重要的理论意义与现实意义,其应用面十分广泛,涉及到通讯网络、计数化学、交通控制等很多方面.1939年Robbins[1]在一篇研究单行道交通系统的论文中证明了“任意一个2-边连通图都有一个强定向”．强定向的最小平均距离作为图的一个重要参数,在结构化学[2]、建筑学[3]、通讯网络等领域都有重要应用,在理论研究方面亦有丰硕的研究成果[4].Plesn’ik[5]、Dankelmann等[6]、周涛等[7]、郝国亮[8]研究了强定向的最小平均距离的上下界.Qian等[9]给出了完全二部图的强定向的最小平均距离的精确值.

目前,大部分文献只给出了一般2-边连通图关于强定向的最小平均距离的一些上下界，而对于特殊图类的强定向的最小平均距离的研究相对较少.本文主要利用图G的σG(v)指标研究含有割点的2-边连通图的强定向的最小平均距离的下界,这些下界部分改进了已有研究结果.

1 预备知识

设G=(V(G),E(G))表示一个n阶无向图,其中V(G)为顶点集,E(G)为边集.相应地,顶点数、边数分别记为|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)指标定义为

σ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.

设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]中给出了如下结论：

引理1[11]若是顶点数为n,边数为m的2-边连通图G的一个强定向,则

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

利用引理1,可以得到如下结论.

定理1 设G是顶点数为n,边数为m的2-边连通图,并设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关于min(G)的下界

本节主要利用定理1给出含有割点的2-边连通图的强定向的最小平均距离的几个下界.

命题1 设G是顶点数为n的块,并设v是G的任意一个顶点,则

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

证明:设eG(v)=d,并设pi=|{x∈V(G):dG(v,x)=i}|(i=1,2,…,d).因为G是块,所以pi≥2(i=1,2,…,d-1)且pd≥1.因此

利用定理1及命题1,可以得到如下结论.

定理2 设G是顶点数为n,边数为m的2-边连通图.若G=G1∪G2且G1∩G2=ω,其中Gi为块(i=1,2),则

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

证明:设Vi=V(Gi),并设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 设G是顶点数为n的块,并设v是G的任意一个顶点,则

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

证明:设eG(v)=d,并设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,可以得到如下结论.

定理3 设G是顶点数为n,边数为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}.

证明:设Di是Gi的一个强定向(i=1,2)，则显然D=D1∪D2是G的一个强定向.注意到n1+n2=n+1.因此,由定理1及命题2可知

设G=G1∪G2且G1∩G2=ω.若G1和G2中至少有一个不是块,则下面将给出μmin(G)的一个下界,为此先给出如下命题.

命题3 设G是顶点数为n的2-边连通图,并设v是G的任意一个顶点,则

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

证明:设eG(v)=d,并设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,可以得到如下结论.

定理4 设G是顶点数为n,边数为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}.

证明:设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].中国科学技术大学学报,2004,34(4):410-413.ZHOUT,XUJM,LIUJ.Extremalproblemondiameterandaveragedistanceofgraphs[J].JournalofUniversityofScienceandTechnologyofChina,2004,34(4):410-413.

[8] 郝国亮.强定向图平均距离的界[J].延边大学学报(自然科学版),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.

(责任编辑：王兰英)

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

国家自然科学基金资助项目(11471273);江西省教育厅科学技术研究项目(GJJ150561);东华理工大学博士科研启动基金资助项目(DHBK2015319；DHBK2015320)

郝国亮(1980—),男,山东肥城人,东华理工大学讲师,博士,主要从事组合图论方向研究. E-mail:guoliang-hao@163.com

O157.5

A

1000-1565(2017)02-0113-04