摘要
对于图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.
出处
《应用数学》
CSCD
北大核心
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)
关键词
凸集
笛卡儿积
测地线
测地数
Convex set Cartesian product Geodesic Geodetic number