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

The Geodetic Numbers of Cartesian Products of Graphs

对于图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.