摘要
文献[1]将3阶以上的连通无向图的顶点扩张图按照其最小定向直径分为三类,并给出了如下猜想:直径至少为3的连通无向图的顶点扩张图不属于第三类图.本文运用顶点标号法,证明了猜想对树是成立的,即树的顶点扩张图的最小定向直径与原树相比最多增加1.
Literature review indicates that some researchers tended to classify the vertex-multiplication graphs corresponding to third-order connected astatic graphs into three categories, and made the hypothesis that the category-Ⅲ graph does not include the vertex-multiplication graph corresponding to the connected astatic graph with its diameter being at lest 3. In this paper, the author has proved that the hypothesis hereinabove goes to trees by employing vertex grading approach： the minimum number of oriented diameter of tree vertex-multiplication graphs has increased by 1 compared with that of the original tree.
出处
《中北大学学报（自然科学版）》
EI
CAS
2006年第2期132-134,共3页
Journal of North University of China(Natural Science Edition)
基金
国家创新研究群体科学基金资助项目(60024301)
山西省自然科学基金资助项目(20051032)
关键词
最小直径定向
树
顶点扩张图
minimum diameter orientation
tree
vertex-multiplication graph
