RP图的特征刻划  

Characterization of Reach-Preservable Graphs

作　　者：李敬杰[1] 李乔[1] 

机构地区：[1]上海交通大学应用数学系,上海200240

出　　处：《上海交通大学学报》2001年第11期1730-1732,1736,共4页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金资助项目 ( 199710 5 6)

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

关 键 词：支撑树 距离 RP图 简单无向连通图 图论 特征刻划 圈 树状结构 

分 类 号：O157.5[理学—数学]