图和有向图的测地数(英文)  

The Geodetic Numbers of Graphs and Digraphs

作　　者：莫艳红[1,2] 吕长虹[1] 叶永升[1,3] 

机构地区：[1]华东师范大学数学系 [2]温州职业技术学院公共教学部,浙江温州325035 [3]淮北煤炭师范学院数学系,安徽淮北235000

出　　处：《应用数学》2007年第4期717-725,共9页Mathematica Applicata

基　　金：Supported by National Natural Science Foundation of China (10301010);Science and Technology Commission of Shanghai Municipality (04JC14031);National Natural Science Founda-tion of Anhui (2006KJ256B)

摘　　要：对于图G(或者有向图D)内的任意两点u和v,u-v测地线是指在u和v之间的最短路(或者从u到v).I(u,v)表示位于一条u-v测地线上所有点的集合,对于SV(G),I(S)表示所有I(u,v)的并,这里u,v∈S.图G(或者有向图D)的测地数g(G)(g(D))是使I(S)=V(G)(I(S)=V(D))的最小点集S的基数.定义G的所有定向图中测地数的最小值为G的下测地数,即g-(G)=min{g(D):D是G的定向图};定义G的所有定向图中测地数的最大值为G的上测地数,即g+(G)=max{g(D):D是G的定向图}.本文的主要目的是研究G∨H的上、下测地数,此外,文章给出了g(G)=g(G×P3)的一个充分必要条件.For any two vertices u and υin a graph G（or digraph D）,a u-υ geodesic is a shortest path between u andυ（or from u to υ）.Let I（u,υ）denote the set of all vertices lying on a u-υ geodesic.For a vertex subset S,let I（S）denote the union of all I（u,υ）for u,υ∈ S.The geodetic number g（G） （or g（D））of a graphG（or digraph D）is the minimum cardinality of a set S with I（S）=V（G）（or I（S）=V（D））.The lower geodetic number of Gis g-（G）=min{g（D）：D is an orientation of G}.The upper geodetic number of G is g＋（G）=max{g（D）：D is an orientation of G}.The main purpose of this papers to study the upper and lower geodetic number of G V H.In addition,a sufficient and necessary condition for g（G）=g（G×P3）is presented.

关 键 词：凸集 笛卡尔积 测地线 测地数 

分 类 号：O157.5[理学—数学]