The graceful numbering, one of the vertex numberings, is considered. The numbering is described as follows; Given a connected graph G(V,E) with $\mid{E}\mid$=e, we wish to assign distinct nonnegative integers to the vertices so that the edge numbers form the set {1,2,$\dots$,e}, where each edge number is defined to be the absolute difference between the numbers assigned to the end vertices of the edge. Moreover, we wish to minimize the maximum value of the vertex numbers. We call this minimized value g(G). If g(G)=e, then G is called to be a "graceful graph," and the numbering achieving g(G)=e, a "graceful numbering." Several workers have extended the area of graceful trees since Ringel conjectured that all trees are graceful.
In this thesis, we shall introduce a sufficient condition for trees to be graceful, and, using it, show that two large classes of trees, "M-trees" including full m-ary trees, m≥1, and "Z-routable trees," are graceful.
본 논문에서는 vertex numbering의 일종인 graceful numbering을 고려하고자 한다. 주어진 그래프 G(V ,E)가 있을 때 ($\mid{E}\mid$=e), 모든 edge number들의 합집합이 $\{1,2,\dots,e\}$를 이루도록 각 vertex에 서로 다른 음이 아닌 정수들을 대응시키고자 한다. 여기서 edge number는 그 edge의 양쪽 끝 vertex에 대응된 數의 差의 절대값이다. 또한, vertex에 대응된 數들의 최대값을 최소화하고자 하며, 이 최소화된 값을 g(G)라고 부른다. 만약에 주어진 그래프 G에 대해서 g(G)=e이면 그 그래프를 graceful 그래프라 하고, g(G)=e를 얻도록 하는 numbering을 graceful numbering이라 한다. Ringel이 모든 tree들은 graceful이라고 추측한 이래 많은 사람들이 이 분야에 대해 연구하여 왔다.
본 논문에서는 tree가 graceful하기 위한 충분 조건을 제시하고, 이를 이용하여 두 가지 종류의 tree --- M-tree(이는 full m-ary tree를 포함)와 Z-routable tree --- 가 graceful임를 보였다.
