RP图的特征刻划

设T是图G的一颗支撑树,若某顶点u满足;对任意顶点υ均有dG(u,υ）=dT(u,υ）,则称u对于支撑树T是RP,如果对G的任一棵支撑树都至少存在一个RP点,则称图G是RP图,Gagliardi等在1997年证明了K2,n是一类RP图,并猜想：“K2,n以及在其顶点上加上若干树状结构所得的图是仅有的RP图”。但容易验证圈Cn也是一类RP图,因此上述猜想需要修正,本文证明了RP图的如下特征刻划：除树外,简单图中只有K2,n和Cn 以及在某若干顶点上分别外接互不相交的树状结构所得的图是RP的。

Characterization of Reach-Preservable Graphs

A vertex v of a spanning tree T of a graph G is called reach preserving if d G(v,w)=d T(v,w) for every vertex w in G . If for every spanning tree of G , there always exists at least one reach preservinig vertex, then G is called reach preservable. In 1997, Gagliardi and Lewinter showed that K 2,n is reach preservable and conjectured that K 2,n 's with tree structures joined to any of their vertices are the only reach preservable graphs. But it is easy to verify that all cycles C n 's are also reach preservable. So their conjecture is defective. This article proved the following characterization for RP graphs: besides trees, K 2,n 's and C n 's with tree structures joined to some of their vertices are the only reach preservable graphs.