图的笛卡儿积的测地数(英文)  

The Geodetic Numbers of Cartesian Products of Graphs

作　　者：叶永升[1] 吕长虹[2] 刘庆敏[2] 

机构地区：[1]淮北煤炭师范学院数学系,安徽淮北235000 [2]华东师范大学数学系,上海200062

出　　处：《应用数学》2007年第1期158-163,共6页Mathematica Applicata

基　　金：Supported by the National Natural Science Foundation of China(10301010),Scienceand Technology Commission of Shanghai Municipality(04JC14031),and National Natural ScienceFoundation of Anhui(2006KJ256B)

摘　　要：对于图G内的任意两点u和v,u-v测地线是指u和v之间的最短路.I(u,v)表示位于u-v测地线上所有点的集合,对于SV(G),I(S)表示所有I(u,v)的并,这里u,v∈S.G的测地数g(G)是使I(S)=V(G)的点集S的最小基数.在这篇文章,我们研究G×K3的测地数和g(G)与g(G×K3)相等的充分必要条件,还给出了T×Km和Cn×Km的测地数,这里T是树.For any two vertices u and v in a graph G, a u-v geodesic is the shortest path between u and v. Let I（u,v） denote the set of all vertices lying on a u-v geodesic. For a vertex subset S, let I（S） denote the union of all l（u,v） for u,v ∈S. The geodetic number g（G） of a graph G is the minimum cardinality of a set S with I（S） = V（G）. In this paper, a sufficient and necessary condition for the equality of g（G） and g（G × K3） is presented, and for a tree T, we give the geodetic number of T × K,, and Cn × Km.

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

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