关于一类新的整和图

On a New Class of Integral Sum Graphs

Ｈａｒａｒｙ 提出了整和图的概念，设 ｆ 为整数集到图 Ｇ（ Ｖ（ Ｇ） ， Ｅ（ Ｇ）） 的顶点集 Ｖ（ Ｇ） 之间的一个单射，使得对于 Ｇ 的两个不同的顶点ｕ 和ｖ ，ｕｖ ∈ Ｅ（ Ｇ） ，当且仅当存在 ｗ ∈ Ｖ（ Ｇ） ，使 ｆ（ ｕ） ＋ ｆ（ ｖ） ＝ｆ（ ｗ ） ，则 Ｇ 称为整和图，并且他证 明了所有路 和星图是整 和图。树 中度数至少 为３ 的 顶点称为 叉点， Ｃｈｅｎ 用粘合法证明了广义星图和叉点距离至少为４ 的树是整和图，并同时猜测所有的树均为整和图。本文证明了所有叉点距离至少为３ 的树是整和图。

The idea of integral sum graph was introduced by Harary. A graph G is called an integral sum graph if its node can be given a labeling f with distinct integers, such that for any two distinct node u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G . He proved that all paths and stars are integral sum graphs. A node of a tree T is called a fork of T if its degree is at least 3. By the method of identification, Chen proved that the generalized stars and the trees which all forks have at least distance 4 are integral sum graphs, and then conjectured that every tree is integral sum graph. That all trees which all forks have at least distinct 3 are integral sum graphs has been proved in this paper.