关于可重构的局部子图

一个图Ｇ在一顶点Ｘ处的局部子图Ｌ｛ｘ｝是由Ｇ的给定性质定义的包含Ｘ的子图Ｌ，并以ｘ为根．例如在点ｘ处的ｋ－局部子图是以ｘ为根，以所有到ｘ距离不超过ｋ的顶点集合｛ｖ∈Ｖ（Ｇ）：ｄＧ（ｖ，ｘ）≤Ｋ｝为顶点集；以｛ｕｖ∈Ｅ（Ｇ）：ｄＧ（ｕ，ｘ）＜ｋ，或ｄＧ（ｖ，ｘ）＜ｋ｝为边集的带根子图．本文证明了：对于Ｇ的局部子图Ｌ｛ｘ｝｝，如果每个Ｌ｛ｘ｝，ｘ∈Ｖ（Ｇ），的顶点数（或边数）都小于Ｇ的顶点数边数）减１，那么Ｇ中同构于每个Ｌ｛ｘ｝的局部子图的个数是（边）可重构的．