Research Doctorate - Doctor of Philosophy (PhD) / In this thesis, a number of new methods for constructing vertex-magic total-labelings of graphs are presented. These represent an advance on existing methods since they are general constructions rather than ad hoc constructions for specific families of graphs. Broadly, five new kinds of construction methods are presented. Firstly, we present a class of methods characterized by adding 2- or 4-factors to a labeled graph, reassigning vertex labels to the edges of these factors and then adding new vertex labels to create a VMTL of the new graph. The major result is a unified method for constructing VMTL of large families of regular graphs, providing strong evidence for MacDougall's conjecture that, apart from a few minor exceptions, all regular graphs possess vertex-magic total-labelings. Secondly, we present methods for obtaining a labeling of a union of two graphs, one of which possesses a strong labeling, and then building on this labeling to create a labeling of an irregular graph. These methods as well as results in the Appendices provide strong evidence against an early conjecture regarding labelings and vertex degrees. Thirdly, constructions are presented for a new kind of magic square, containing some zeroes, which can be used to build labelings of graphs from labeled spanning subgraphs. Next, constructions are presented for a new kind of anti-magic square, containing some zeroes, which is equivalent to a strong labeling of certain kinds of bipartite graphs which can in turn be built upon to produce labelings of graphs with more edges. Finally, we present a method of mutating a graph labeling by reassigning edges in a way that preserves the magic constant to obtain a labeling of a different graph. This method provides a prolific source of new labelings.
| Identifer | oai:union.ndltd.org:ADTP/280714 |
| Date | January 2006 |
| Creators | Gray, Ian |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Copyright 2006 Ian Gray |
Page generated in 0.0018 seconds