关于连通中心数与连通控制数参量下图的平均距离与极值图的刻画

发布时间：2018-04-04 02:02

  本文选题：平均距离　切入点：2-连通　出处：《兰州大学》2017年硕士论文

【摘要】：设G是连通图,顶点集为V(G),边集为E(G),S是G的一个顶点子集.若S'外的任意一对不相邻的点都可由一条内点都在S中的路相连,则我们称S是G的一个中心集.进一步地,若S导出的子图是连通的,就称其为连通中心集.最小中心集的阶称为中心数,记为h(G);最小连通中心集的阶称为连通中心数,记为hc(G).若S外的任一点都与S中的某个点相邻,且S导出的子图是连通的,则我们称S是G的一个连通控制集.类似地,定义连通控制数γ_c(G).图G的直径用d(G)表示.本文完成了不等式h(C)≥d(G) - 1取等号时对应极值图的刻画.其次,根据参量h_c(G)与γ_c(G)之间的联系:hc(G) ≤ γ_c(G)≤h_c(G) + 1,我们将图分为两类,并按这种分类方式分别给出图G关于h_c(G)的平均距离的上界以及相应极值图的刻画.作为推论,我们对一般的给定顶点数的连通图G分别给出了其关于h_c(G)与γ_c(G)的平均距离的上界.进一步地,本文又将图G限制为2-连通图,并得到结论:2-连通的边极小图的最小连通控制集导出的子图一定是树.特殊地,当限制γ_c(G) = 2时,我们给出了 2-连通图G的平均距离的上界,并刻画了相应极值图.
[Abstract]:Let G be a connected graph, the vertex set is a VG G, and the edge set is a vertex subset of G.If any pair of nonadjacent points outside S 'can be connected by a path in S, then S is called a central set of G.Furthermore, if the subgraph induced by S is connected, it is called the connected center set.The order of the minimum center set is called the center number, and the order of the minimum connected center set is called the connected center number.If any point outside S is adjacent to a point in S and the subgraph induced by S is connected, then S is a connected dominating set of G.Similarly, we define the connected domination number 纬 C / G ~ (1).The diameter of figure G is denoted by dg.In this paper, we have completed the characterization of the corresponding extremal graphs when the inequality hu C 鈮，

本文编号：1707882