No description available.

No description available.

No description available.

The vertex separation of a graph is the minimum vertex separation of a linear layout of that graph over all its linear layouts. A linear layout of a graph is an arrangement of its vertices in a line and the vertex separation of a linear layout is maximum number of vertices to the left of any intervertex "gap" that are adjacent to vertices to the right of that gap, over all gaps. A unicyclic graph is a connected graph with precisely one cycle that is, a tree plus an extra edge. We present a O(n lgn) algorithm to compute the optimal vertex separation of unicyclic graphs. The algorithm is "practical" in the sense that it is easily implementable. Furthermore, the algorithm outputs a layout for the unicyclic graph of minimum vertex separation.

No description available.

Ph.D. (Mathematics) / Please refer to full text to view abstract

M.Sc. (Mathematics) / Please refer to full text to view abstract

The n-antiprism graph is not widely studied as a class of graphs in graph theory hence there is not much literature. We begin by de ning the n-antiprism graph and discussing properties, which we prove in the thesis, and which have not been previously presented in graph theory literature. Some of our signi cant results include proving that an n-antiprism is 4-connected, 4-edge connected and has a pathwidth of 4. A highly studied area of graph theory is the chromatic polynomial of graphs. We investigate the chromatic polynomial of the antiprism graph and attempt to nd explicit expressions for the chromatic polynomial of the antiprism graph. We express this chromatic polynomial in several forms to discover the best-suited form. We then explore the Tutte polynomial and search for an explicit expression of the Tutte polynomial of the antiprism graph. Using the relationship between a graph and its dual graph, we provide an iterative expression of the Tutte polynomial of the antiprism graph.

Firstly we express the chromatic polynomials of some graphs in tree form. We then Study a special product that comes natural and is useful in the calculation of some Chromatic polynomials. Next we use the tree form to study the chromatic polynomial Of a graph obtained from a forest (tree) by "blowing up" or "replacing" the vertices Of the forest (tree) by a graph. Then we give explicit expressions, in terms of induced Subgraphs, for the first five coefficients of the chromatic polynomial of a connected Graph. In the case of higher order graphs we develop some useful computational Techniques to obtain some higher order coefficients. In the process we obtain some Useful combinatorial identities, some of which are new. We discuss in detail the Application of these combinatorial identities to some families of graphs. We also discuss Pairs of graphs that are chromatically equivalent and graph that are chromatically Unique with special emphasis on wheels. In conclusion,

Lau, Siu Cheong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 51-52). / Abstracts in English and Chinese. / Chapter 1 --- In search of minimal cycles --- p.9 / Chapter 1.1 --- What do we mean by cycles? --- p.9 / Chapter 1.2 --- Integral currents --- p.10 / Chapter 1.3 --- Calibration theory --- p.13 / Chapter 2 --- Motivation from the Hodge Conjecture --- p.17 / Chapter 2.1 --- Hodge theory on Riemannian manifolds --- p.17 / Chapter 2.2 --- Hodge decomposition in Kahler manifolds --- p.19 / Chapter 2.3 --- The Hodge conjecture --- p.22 / Chapter 3 --- Variation of cycles in symmetric orbit --- p.26 / Chapter 3.1 --- Variational formulae --- p.26 / Chapter 3.2 --- Stability of cycles in Sm and CPn --- p.29 / Chapter 3.3 --- Symmetric orbit in Euclidean space --- p.31 / Chapter 3.4 --- Projective spaces in simple Jordan algebra --- p.39 / Chapter 3.4.1 --- Introduction to simple Jordan algebra --- p.39 / Chapter 3.4.2 --- Projective spaces as symmetric orbits --- p.41 / Chapter 3.4.3 --- Computation of second fundamental form --- p.43 / Chapter 3.4.4 --- The main theorem --- p.45 / Chapter 3.5 --- Future directions --- p.49 / Bibliography --- p.51