本文選題：平均距離　切入點(diǎn)：2-連通　出處：《蘭州大學(xué)》2017年碩士論文

【摘要】：設(shè)G是連通圖,頂點(diǎn)集為V(G),邊集為E(G),S是G的一個(gè)頂點(diǎn)子集.若S'外的任意一對(duì)不相鄰的點(diǎn)都可由一條內(nèi)點(diǎn)都在S中的路相連,則我們稱S是G的一個(gè)中心集.進(jìn)一步地,若S導(dǎo)出的子圖是連通的,就稱其為連通中心集.最小中心集的階稱為中心數(shù),記為h(G);最小連通中心集的階稱為連通中心數(shù),記為hc(G).若S外的任一點(diǎn)都與S中的某個(gè)點(diǎn)相鄰,且S導(dǎo)出的子圖是連通的,則我們稱S是G的一個(gè)連通控制集.類似地,定義連通控制數(shù)γ_c(G).圖G的直徑用d(G)表示.本文完成了不等式h(C)≥d(G) - 1取等號(hào)時(shí)對(duì)應(yīng)極值圖的刻畫(huà).其次,根據(jù)參量h_c(G)與γ_c(G)之間的聯(lián)系:hc(G) ≤ γ_c(G)≤h_c(G) + 1,我們將圖分為兩類,并按這種分類方式分別給出圖G關(guān)于h_c(G)的平均距離的上界以及相應(yīng)極值圖的刻畫(huà).作為推論,我們對(duì)一般的給定頂點(diǎn)數(shù)的連通圖G分別給出了其關(guān)于h_c(G)與γ_c(G)的平均距離的上界.進(jìn)一步地,本文又將圖G限制為2-連通圖,并得到結(jié)論:2-連通的邊極小圖的最小連通控制集導(dǎo)出的子圖一定是樹(shù).特殊地,當(dāng)限制γ_c(G) = 2時(shí),我們給出了 2-連通圖G的平均距離的上界,并刻畫(huà)了相應(yīng)極值圖.
[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 鈮，

本文編號(hào)：1707882