用σG(v)表示图G中顶点v与G中所有顶点间的距离之和.利用σG(v)指标得到了含有割点的2-边连通图G的强定向的最小平均距离的若干下界.
Let σG(v)denotes the sum of the distance between the vertex of and all of the vertices of G.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 graph G with at least a cut vertex were established.
[1] ROBBINS H E.A theorem on graphs with an application to a problem of traffic control[J].Am Math Mon,1939,46:281-283.
[2] DOYLE J K.Mean distance in a graph[J].Discrete Math,1977,17:147-154.
[3] CHUNG F R K.The average distance and the independence number[J].Journal of Graph Theory,1988,12:229-235.
[4] KOH K M,TAY E G.Optimal orientations of graphs and digraphs:a survey[J].Graphs and Combinatorics,2002,18:745-756.
[5] PLESNIK J.On the sum of all distances in a graph or digraph[J].Graph Theory,1984,8:1-21.
[6] DANKELMANN P,OELLERMANN O R,WU J L.Minimum average distance of strong orientations of graphs[J].Discrete Applied Mathematics,2004,143:204-212.
[7] 周涛,徐俊明,刘隽.图直径与平均距离的极值问题研究[J].中国科学技术大学学报,2004,34(4):410-413. ZHOU T,XU J M,LIU J.Extremal problem on diameter and average distance of graphs[J].Journal of University of Science and Technology of China,2004,34(4):410-413.
[8] 郝国亮.强定向图平均距离的界[J].延边大学学报(自然科学版),2008,34(4):238-239. HAO G L.Bound of the average distance of the strong orientations[J].Journal of Yanbian University(Natural Science Edition),2008,34(4):238-239.
[9] QIAN J G,ENGEL K,XU WI.A generalization of Sperner’s theorem and an application to graph orientations[J].Discrete Applied Math,2009,157:2170-2176.
[10] BONDY J A, MURTY U S R. Graph Theory[M]. New York:Springer, 2008.
[11] NG C P,TEH H H.On finite graphs of diameter 2[J].Nanta Math,1966,67(1):72-75.
