关于局部子图可重构性的一个新结果(英文)

A New Result on Reconstructible Local Subgraphs

本文研究局部子图的可重构性．一个图Ｇ在一顶点ｖ处的ｋ－局部子图是到ｖ距离小于等于ｋ的顶点导出且以ｖ为根的子图，记为ＬｋＧ（ｖ）．本文通过引进核子图的结构证明了ｋ－局部子图是可重构的，如果每一个ｋ－局部子图所含的顶点数都小于等于｜Ｖ（Ｇ）｜－１．这个结果改进了原有的结果．由这个新结果可知，图的半径这个参数是可重构的．本文还提出了点距序列的概念，并进一步讨论了点距序列与局部子图的关系和一些未解决的问题．

A k -local subgraph of graph G at a vertex v , denoted by L G k(v) , is a subgraph of G rooted at v and induced by the set {x∈V(G): d G(v,x)k} . In this paper, a special kind of spanning graphs, called weighted nuclear subgraphs is introduced and it is proved that the number of k -local subgraphs of G which are isomorphic to a given local subgraphs is reconstructible, if the number of vertices of every k -local subgraph of G is less than υ(G) . This improves the main result in a previous paper published by the same authers in 1996, and as a consequences of this new result, we know that the radius of a graph is reconstructible.