Методы построения квадратной разностной разметки

Abstract

Предложен конструктивный метод построения квадратных разностных деревьев, основанный на методе Δ-построения грациозных деревьев и методы построения таких деревьев больших размеров, имеющих три подхода.

Запропоновано конструктивний метод побудови квадратних різницевих дерев, заснований на методі Δ-побудови граціозних дерев та методи побудови таких дерев великих розмірів, які мають три підходи.

Introduction. The urgency of the graceful labeling of graphs, namely, the problem of Kotzig-Ringel Rosa brought a wave of different methods of labeling graphs. In particular, one of the constructive approach of finding graceful trees of large size from the known graceful trees was offered by R. Stanton, C. Zarnke, K. Koh, D. Rogers, T. Tan. K. Koch, D. Rogers and T. Tan have completed the construction of a new graph, adding to the disjunctive union of isomorphic copies of a given graceful graph T an additional vertex connected by its edges to isomorphic images of some fixed vertex of T. This method is used to study gracefulness of the symmetrical trees. The same authors generalized this method by identifying isomorphic images of a fixed vertex of T, with the additional vertex. The construction of a graceful tree is implemented for a given pair of graceful trees and named Δ-constructing. Using it, K. Koh and others proved gracefulness of full m-arch tree. Methods and results. The methods of construction of square difference trees are applied. A new square difference tree is built from one square difference tree by identifying vertices with the greatest label of the isomorphic copies of the tree and using a new vertex and edges connecting the isomorphic copies of the square difference of a tree with the vertex. A method of Δ-constructing a square difference tree from two square difference trees is used. Conclusion. The class of square differential trees is expanded. Methods used to build square difference tree can be applied in further theoretical studies.