对边幻图猜测的一个证明

令简单图G =(V ,E)是有 p个顶点 q条边的图。假设G的顶点和边由 1 ,2 ,3 ,… ,p + q所标号 ,且 f :V∪E { 1 ,2 ,… ,p + q}是一个双射。如果对所有的边xy ,f(x) + f(y) + f(xy)是常量 ,则称图G是边幻图 (edge-magic)。毛毛虫图是一个树 ,移走它的所有端点产生一个路 (称为T的脊或主干 )。例如 ,路和星图是毛毛虫图。证明了毛毛虫图是边幻图 ,从而证明了顶点不超过 8的树是边幻图。

A Proof of the Conjecture About Edge-Magic Graph

Let G be a graph with p vertices and q edges. Assume the vertices and edges of G are labelled by 1,2,3, …, p+q such that each label is used exactly once. We define the valence of an edge to be the sum of the label of e plus the two labels of the vertices incident with e. If a labelling of G is possible such that the valence for e is constant, we call the graph G is edge-magic. A caterpillar T is a tree in which the removal of all end-nodes results in a path(called the spine of T). For examples, the paths and the stars are catepillars. In this paper, we prove catepillars are edge-magic. So we prove that the tree with at most 8 nodes is edge-magic.