郝国亮,谢智红

(东华理工大学 理学院,江西 南昌 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)指标定……