【作者】 莫艳红；

【导师】 吕长虹；

【作者基本信息】 华东师范大学 ， 运筹学与控制论， 2007， 硕士

【摘要】 图的测地数是揭示图的结构特性的一个重要参数。图的测地数源于几何学、拓扑学和函数分析中的凸集理论，是凸集理论在图论中的应用和推广，也与图论中“路覆盖”和“路分解”等问题相关联。本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工作，主要的工作包括以下四个部分：（1）给出图的最小测地集与割点之间的关系；（2）讨论了图T_n（K_d）和T_n（C_d）的测地数；（3）研究了G∨H的测地数及其上测地数和下测地数；（4）讨论了G×P₃的测地数。在第二章中，介绍了无向图的测地数，我们主要做了以下的工作：我们研究了含有割点的图的测地集，并得到相关结论：图的最小测地集都不包含它的割点，这个结论是对文献[8]中有关树T_n测地数这一内容的推广；在[8]中，Grary Chartrand，Frank Harary和Ping Zhang证明了g（K_n）=n，我们推广了这个结论得到：如果图G有n≥3个顶点和k个割点，并且G的每个块都是完全图，那么g（G）=n-k。我们定义了一个新图T_n（H）。若T_n表示顶点为n≥2的树，H为一个图，则T_n（H）表示如下构造得到的图：用图H来替代T_n中所有的顶点，若H_u，H_v分别表示代替T_n中相邻顶点u，v的图H，则用边xy来代替T_n的边uv，其中x∈V（H_u），y∈V（H_v）。并且证明了以下结论：●如果T_n是有n≥2个顶点，l片叶子的树，那么g（T_n（K_d））=ld；如果T_n不是星图，且T_n有l片树叶，d≥4，n≥3，那么g（T_n（C_d））≤min{「d／2」l，2（n-l）}。在第三章中，讨论了有向图的测地数，我们主要研究了G∨H的上（下）测地数及和测地数之间的关系，证明了下列结果：●对于任意图G和H，有g^-（G∨H）=2。如果G和H是两个非平凡图，那么g⁺（G∨H）≥g⁺（G）+g⁺（H）。在文献[1]中，吕长虹提出了一个关于图的测地数的猜想：对于任意图G，都有g⁺（G）≥g（G），并且证明了当d是n阶连通图的直径且d≥（n-1）／2或g（G）≤4时，这个猜想是正确的，我们主要研究了G∨H的上测地数和测地数之间的关系，并且证明了：●如果G和H都不是完全图，那么g⁺（G∨H）≥g（G∨H）；如果H是完全图，G是弦图或ω（G）＜3，那么g⁺（G∨H）≥g（G∨H）；假设S是G的最小2-N-控制集，如果H是完全图，S中每一点在G／S中至多只有一个邻居，那么g⁺（G∨H）≥g（G∨H）。在第四章中，讨论了图的笛卡儿积的测地数。在文献[1]中，吕长虹给出了g（G）=g（G×K₂）的充要条件，我们考察了当g（H）=2时G×H的测地数，得出了下列结论：●如果存在最小测地集S和基于S的测地族F使得S相对于F分成（S₁，S₂），那么对任意测地数为2的图H有g（G）=g（G×H）。●设G是不平凡的连通图，那么g（G）=g（G×P₃）当且仅当存在最小测地集S和基于S的测地族F使得S相对于F分成（S₁，S₂，S₃）或（S₁，S₂）。更多还原

【Abstract】 The geodetic number of a graph is an important parameter revealing the structural character of graphs. The geodetic number of a graph originated from the convex set theory of geometry, topology and functional analysis, and is the generalization and application of convex set theory in graph theory; There is an important relation between the geodetic number of a graph and the problems of path covered and path decomposed.In this thesis, we will consider the geodetic number of graphs and digraphs, and research results of mine are mainly presented. The content of the thesis mainly involve the following four parts: （1） The relation between the minimum geodetic set and cut-vertices of a graph is given; （2） The geodetic numbers of the graph T_n（K_d）and T_n（C_d） are discussed; （3） Studying the geodetic number and the upper （lower） geodetic number of the graph G ∨ H; （4） The geodetic number of the graph G × P₃ is discussed.In Chapter 2, we investigate the geodetic number of undirected graph. We obtain the following results.We discuss the geodetic set of graphs containing cut-vertices, we obtain the following results: every minimum geodetic set of a graph does not contain its cut-vertices, this result is the generalization of the result on the geodetic number of T_n in [8]; In [8], Grary Chartrand, Frank Harary and Ping Zhang prove that g（K_n） = n, we show that if G is a graph with n ≥ 3 vertices and k cut-vertices, and every block of G is a complete graph, then g（G） = n- k.We define a graph T_n（H）: a graph T_n（H） is a graph obtained from a tree T_n with n ≥ 2 vertices by replacing all the vertices v ∈V（T_n） and the edges uv∈ E（T_n） by E（H_u ∨ H_v）, where H_u is a graph H replacing u and H_v is a graph H replacing v. And prove the following results.If T_n is a nontrivial graph with l leaves, then g（T_n（K_d）） = ld;If T_n is a star graph,then If T_n is not a star graph and T_n has l leaves, d ≥ 4 and n ≥ 3, then g（T_n（C_d）） ≤min{「d/2（?）l,2（2-l）} .In Chapter 3, we discuss the geodetic number of digraphs. The lower and upper geodetic number of G∨H and the relation between the geodetic number and the upper geodetic number of G∨ H are studied. We obtain the following results.For any two graphs G and H, we have g （G∨ H） = 2.If G and H are two nontrivial graphs, then g⁺（G∨H）≥ g⁺（G） + g⁺（H）.In [1], Lu raised a conjecture that g⁺（G） ≥ g（G） for any graphs of order n withg（G） ≤ 4 or its diameter no less than （n - 1）/2. We study the relation between g⁺（G ∨H） and g（G ∨ H）, and prove the following results.If neither G nor H is a complete graph then g⁺（G∨H） ≥ g（G ∨H）.If H is a complete graph and G is a chordal graph or G is a graph with ω（G） < 3, then g⁺（G∨H）≥g（G∨H）.Suppose that S is a minimum 2- N - dominating set of G. If every vertex of S has at most one neighbor in G/S and H is a complete graph, then g⁺（G∨H） ≥ g（G∨H）.In Chapter 4, we discuss the geodetic number of cartesian product graphs. In [1], Lu raised a sufficiant and necessary condition for g（G） = g（G ×K₂）, we study the geodetic number of G × H with g（H） = 2, and obtain the following results. If there exists a minimum geodetic set S and a family F based on S relatives to F can be partition into （S₁, S₂）, then g（G） = g（G × H） for any graph H with g（H） = 2. If G is a nontrivial connected graph, then g（G） = g（G× P₃） if and only if there exists a minimum geodetic set S and a family F based on S such that S relatives to F can be partition更多还原