Sherman Z. Extreme labeling of vertices and edges of graphs

The thesis is devoted to the problem of libeling’s graphs of different classes and types. The analysis and systematization of methods of constructing graceful labeling of graphs, which is historically the first labeling and underlies finding other types of labeling, is carried out. As a result of the analysis, the main universal and special methods for constructing graceful labeling of graphs are highlighted. Specific methods include: the method of transferring branches and edges, the method of Δ-construction, functional dependence and recursive method. The universal methods include: the method of integer programming. In addition, the conditions for the existence of Fibonacci graceful, square sum and square difference labeling are found. Methods of constructing them for new classes of graphs are developed. A set of tasks for the existence of Fibonacci graceful labeling for some graphs of a cyclic structure is formulated and solved. Namely for the following graphs: path union of cycles, one-point union of cycles, arbitrary path union of cycles, graph nCm. The methods of constructing a square sum labeling for the following graphs are developed: one-point union of any square total graph with a path, an edge union of n copies of a C3 cycle and a path, a graph obtained as a result of path union of cycles, a total path graph and a disjoint union of any number of square sum graphs. New results are received related to the methods of constructing square difference labeling for the following graphs: one-point union of cycles Cm for any odd m, onepoint union of n copies of the cycle Cm and n copies of the path P2, disjoint union of one-point union of n copies of the Cm cycle with the Pn path, the caterpillar graphs, the point union of cycles, the disjoint union of stars, and the disjoint union of any SD graph with the path. The hypothesis of the existence of a square difference labeling for a cactus cycle is proved. In the dissertation, new results are obtained related to the methods of constructing new square-difference trees from known square-difference trees. To construct a new tree, the method of Δ-construction and its three main approaches are chosen: the identification of vertices with the largest label of isomorphic copies of one square-difference tree; use of a new vertex and edges that connect isomorphic copies of one square-difference tree; method of Δ-construction, using two square difference trees.