Petreniuk D. Methods of solving the problem of decomposing complete graphs into sub-graphs

The thesis is devoted to decomposition of K13 into cubic components of specified type, and to complete graph half-rotational T factorization - methods of obtaining the factorizations, conditions of their existence and their connection to vertex labeling of trees. For K13 we studied existence of the decompositions where any two components of the same order are isomorphic, then the decompositions where components of the same order are not necessarily isomorphic, and also the decompositions with one component isomorphic to Petersen's graph. We prove that all half-symmetrical trees of orders 18, 20, 22 admit half-rotational T factorization of the corresponding complete graph. To prove this we use the notion of graceful labelling of a tree. The problem of finding T factorization for a given half-symmetrical tree can be reduced to finding graceful labeling for the symmetrical half of that tree. We also suggest new methods to obtain graceful labeling for definite classes of trees - l-star, (2, k)-caterpillar, p snowflake. Gracefulness is proven and a graceful labeling method of obtaining is shown for a new classes of trees - even lobsters and r-caterpillars.