一类强定向的最小平均距离
|
摘要
用σ_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.
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]PLESN’IK 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.
[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]PLESN’IK 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.