含有割点的图的测地集

对于图G内的任意两点u和v,u-v测地线是指在u和v之间的最短路．I（u，v）表示位于一条u-v测地线上所有点的集合，对于S包含V（G），I（S）表示所有，（u，v）的并。这里u，u∈S．G的测地数g（G）是使I（S）=V（G）的最小点集S的基数．图的每个最小测地集都不包括它的割点，如果图G是一个有n≥3个顶点，k≥1个割点的块图．那么g（G）=n-k．树T有n≥2个顶点，l片叶子。如果将树T的所有点ui用图Hi来代替。用Hi∨Hj来代替树T的所有边uivj∈E（T），将得到的新图定义为Tn（H）。有g（Ta（Kd））=ld和g（Tm（Cd））≤min{d/2]l。2（n-l）}/．

The Geodetic Set of Graphs Containing Cut-vertices

For any two vertices u and v of a graph G,a u-v geodesic is the shortest path between u and v.The set I(u,v) consists of all vertices lying on a u-v geodesic.For S()V(G),I(S) is the union of all sets I(u,v) for vertices u,v∈S.The geodetic number g(G) is the minimum cardinality among the subsets S of V(G) with I(S)=V(G).It is shown that every minimum geodetic set of a graph does not contain its cut-vertices, and if G is a block graph with n≥3 vertices and k≥1 cut-vertices,then g(G)=n-k.Tn(H) is a graph obtained from a tree T with n≥2 vertices and l leaves by replacing all the vertices vi of the tree with graph Hi and replacing all the edges vivj∈E(T) by Hi∨Hj.It is shown that g(Tn(Kd))=ld and g(Tn(Cd))≤min{「d/2(「)l,2(n-l)}.