This master’s thesis in graph theory focuses on graph decomposition. In practice, various forms of graph decomposition often appear in problems of arranging objects in groups with special characteristics, which is why we come across them in various fields, ranging from computer algorithms to social networks and mathematical puzzles.
Graph decomposition is a union of subgraphs such that every edge of the graph belongs to exactly one subgraph. In the thesis, we examine various types of decompositions. If the subgraphs are isomorphic, we talk about an isomorphic graph decomposition. A special form of decomposition is factorisation. In this case, the graph is decomposed into spanning subgraphs. A special case of factorisation is k-factorisation, i.e., a decomposition of a graph into k-regular spanning subgraphs. When k=1, the graph is decomposed into 1-factors, which are also called perfect matchings. So 1-factorisation is a decomposition of a graph into the largest possible number of isomorphic factors, while 2-factorisation is a decomposition of a graph into a union of cycles. For illustration and a better understanding, we provide examples of graph decomposition and factorisation.
In the thesis, we examine in particular the isomorphic factorisation of complete graphs. We give the proof of the Divisibility Theorem proven by Harary, Robinson and Wormald [8]. The Divisibility Theorem states that a complete graph of order n can be decomposed into t isomorphic factors if and only if t divides the number of edges of the complete graph. The proof of the theorem is constructive and includes a description of the construction of the appropriate factors for different values of parameters n and t. In the chapter on tridivisibility, we illustrate the use of this theorem by defining all nine tridivisions of the complete graph K6 and describing how we would find all 41 tridivisions of the complete graph K7.
Further below we show some theorems about isomorphic decomposition of complete graphs into the greatest possible number of factors (1-factorisation), two isomorphic factors (self-complementary graphs), paths and cycles (2-factorisation). In the case of cycle decomposition, a complete graph can be decomposed into Hamiltonian cycles, cycles of arbitrary length and the shortest 3-cycles. The problem of decomposing complete graphs into 3-cycles is connected to the Steiner triple systems, so to the question of how many triplets we can make with given elements so that any pair of elements is contained in exactly one of the triplets. The decomposition of a graph into cycles of arbitrary length is at the centre of Alspach's conjecture, which was recently confirmed by D. Bryant et al. [5].
In the research of graph decomposition, there are still many unsolved conjectures. One of them is mentioned in the thesis and it refers to the decomposition of complete graphs into isomorphic subgraphs of given forms, for example, trees. Ringel and Kotzig have found that a complete graph of order 2n+1 can be decomposed into subgraphs of size n if the subgraph has a special characteristic that we today call ``gracefulness''. The conjecture is that all trees are graceful.
In the end there are shown some combinatorical puzzles, which we can use at math class.
|
