图和有向图的测地数

对于图G（或者有向图D）内的任意两点u和υ,u-υ测地线是指在u和υ之间的最短路（或者从u到υ）.I（u,υ）表示位于一条u-υ测地线上所有点的集合,对于S（U∣）V（G）,I（S）表示所有I（u,υ）的并,这里u,υ∈S.图G（或者有向图D）的测地数g（G）（g（D））是使J（S）=V（G）（J（S）=V（D））的最小点集S的基数.定义G的所有定向图中测地数的最小值为G的下测地数,即g-（G）=min{g（D）：D是G的定向图）;定义G的所有定向图中测地数的最大值为G的上测地数,即g＋（G）=max{g（D）：D是G的定向图）.本文的主要目的是研究G V H 的上、下测地数,此外,文章给出了g（G）=g（G×P3）的一个充分必要条件.

The Geodetic Numbers of Graphs and Digraphs

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.