Graph decompositions, theta graphs and related graph labelling techniques

Blinco, Andrew. (2003). Graph decompositions, theta graphs and related graph labelling techniques PhD Thesis, School of Physical Sciences, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE17271.pdf Full text application/pdf 7.75MB 7
Author Blinco, Andrew.
Thesis Title Graph decompositions, theta graphs and related graph labelling techniques
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2003
Thesis type PhD Thesis
Supervisor Dr E. J. Billington
Total pages 190
Collection year 2003
Language eng
Subjects L
230101 Mathematical Logic, Set Theory, Lattices And Combinatorics
780101 Mathematical sciences
Formatted abstract
In recent years much work has been done on finding edge-disjoint decompositions of a complete graph on v vertices, Kν, into copies of certain graphs. In particular, the problem of finding decompositions of complete graphs into cycles of length n, Cn, has received much attention, and this problem was solved for many cases by Kotzig, Rosa, Hoffman, Lindner and Rodger. Recently, the necessary conditions for the existence of a decomposition of the complete graph into cycles of a fixed length have been shown to be sufficient by Alspach, Gavlas and Sajna. For any graph G the set of values of v for which there exists a G-decomposition of Kν (also called a G-design of order v) is called the spectrum for G-designs.

In this thesis we consider the spectrum problem for certain theta graphs. A theta graph is a simple graph consisting of two vertices joined by a number of internally disjoint paths, and we denote it here by θ(l1,l2,…,lt), where l1,l2,…,lt are the lengths of the paths. This notation for theta graphs was introduced by Loerinc in 1978. As an example, K4 — e, a complete graph on four vertices missing one edge, is a theta graph consisting of four vertices, with two vertices joined by one path of length one and two paths of length two, denoted by θ ( 1 , 2, 2). Moreover, note that the graphs Km+2 \ Km constitute a family of theta graphs, θ (1, 2, 2 , . . . , 2). Many properties of the graph K4 — e (and also the graphs Km+2 \ Km) have been investigated. Also, the graphs K2,m form another family of theta graphs, θ (2, 2 , . . . , 2). The spectrum problem for theta graphs consisting of three paths will be the focus of much of this thesis. Theta graphs of the form θ (l1,l2,l3) may be thought of as an edge-amalgamation of two cycles of length li + lj and li + lk, with li edges in common, where (i,j, k) is some permutation of (1,2,3). Continuing with the previous example, θ (1, 2, 2) may be thought of as an amalgamation of two cycles of length three, with one edge in common.

Unlike cycle designs, the obvious necessary conditions for the existence of a theta graph design are not always sufficient; and this lack of sufficiency in certain cases is investigated in Chapter 2.

In Chapters 3, 4 and 5 we complete the spectrum problem for theta graphs with fewer than ten edges. Many of the necessary examples (which appear in Appendix A) used these in chapters were found using autogen, a graph decomposition software package written by Adams.

A decomposition of Kν\L, the complete graph of order v with the edges of a subgraph L (called the leave) removed, into edge disjoint copies of a graph G is called a maximum packing of with G if L contains as few edges as possible. A decomposition of Kν U X with V(X) C V(Kν), the complete graph of order v union a graph X (called the excess), into edge disjoint copies of a graph G is called a minimum covering of Kν with G if X contains as few edges as possible. The maximum packing and minimum covering problems have been studied for many graphs. In Chapter 6 we construct maximum packings and minimum coverings of Kν with copies of θ (1,3,3) for all ν‡ 0 or 1 (mod 7), where L and X are compact (that is, are simple graphs on the least number of vertices). The necessary examples required for the constructions given in this chapter can be found in Appendix B. (When ν = 0 or 1 (mod 7), the leave or excess is empty, and a decomposition of Kν in this case into θ(1,3,3) is covered by the results of Chapter 3.)

In Chapters 7, 8 and 9 we present some general constructions for theta graph decompositions. In Chapter 7, methods for decomposing the complete graph Kν into theta graphs of the form θ(1, n, n) are given when ν Ξ 0(mod 2n + 1) if n is odd, and when ν Ξ 1 (mod 2n + 1) if n Ξ 3 (mod 4); in the case n Ξ 1 (mod 4) further partial results are obtained. In Chapter 8, methods for decomposing the complete graph Kν into theta graphs of the form θ(1, n, n) are given when ν Ξ l (mod 2n -I-1) and n Ξ 2 (mod 4). In Chapter 9, methods for decomposing the complete graph Kν into theta graphs of the form θ(1, 2m, 2n - 2m) are given when νΞ2n + 1, 2n +2,4n + 3, 6n + 3,6n + 4 (mod 8n + 4) and n is odd.

For any graph G, an injective function h : V(G) -> N is called a labelling (or a valuation) of G. In 1966, Rosa introduced a hierarchy of labellings, including ρ-, β and α-labellings. In Chapters 10 and 11 some new types of labellings are added to this hierarchy. The concept of an ordered ρ-labelling (denoted ρ+) was introduced by El-Zanati, Vanden Eynden and Punnim. As with the case of an α-labelling, a ρ+-labelling of a graph G with n edges yields a cyclic G-decomposition of K2nx+1 for all positive integers χ. It was shown by El-Zanati et al. that the disjoint union of a collection of graphs with α-labellings has a p+-labelling. In Chapter 10 we show that the disjoint union of a collection of graphs with α-labellings together with a graph with a slightly restricted ρ+-labelling (called a p++-labelling) also has a p++-labelling. This result has an application to the cyclic decomposition of certain complete graphs into the disjoint union of even-length cycles.

An almost-bipartite graph is a non-bipartite graph with the property that the re-moval of a (possibly particular) single edge renders the graph bipartite. Examples of such graphs include odd cycles and the graphs Km+2 \ Km. The technique of labelling the vertices of bipartite graphs to yield decompositions of certain complete graphs has received much attention in the literature. In Chapter 11 we introduce the concept of a γ-labelling of an almost-bipartite graph and show that if an almost-bipartite graph G with n edges has a γ-labelling then there is a cyclic G-decomposition of K2nx+1 for all positive integers x. We show that odd cycles and certain other almost-bipartite graphs have γ-labellings.

In Chapter 12, we combine the results concerning theta graph designs with the results concerning the labelling of the vertices of graphs by giving α-labellings of some bipartite theta graphs and 7-labellings of some almost-bipartite theta graphs.

In Chapter 13, a small result concerning Eulerian circuits and the regular icosahedron is presented.

Finally, in Chapter 14 we summarise the results of this thesis.
Keyword Paths and cycles (Graph theory).
Graph labelings.

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
 
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 24 Aug 2007, 18:08:10 EST