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

關於有唯一禁子圖的改邊問題的多項式核心無H加/删/加删邊問題求是否可能加/删/加删至多k條邊於一圖使其無任何與H同構的誘導子圖。此乃計算機科學基本問題之一，其研究廣泛。此題對任意固定H為NP完全且固定參數可解。本文研究無H改邊問題之多項式核心；其存在視H之結構而定。之分類在當H為一圈，路徑或三聯通圖時則完全，當H為删一邊於完全圖之結果時則近完全，當H為樹時則部分此結果加強對無H改邊問題之認識。本文的思路與工具益未來研究，或有助於無H改邊問題多項式核心存在二分定理之發現。 / The H-free edge completion (deletion, editing) problem asks whether it is possible to add to (delete from, add to and delete from) a graph at most k edges so that no induced sub graph isomorphic to H remains. These problems are fundamental in computer science and were studied extensively. They are NP-complete and fixed-parameter tractable for every fixed H. / In this thesis, we study polynomial kernels for H-free edge modification problems, as their existence depends on the structure of H. We characterise their existence completely when H is a path, cycle or 3-connected graph, almost completely when H is one edge short of a complete graph, and partially when H is a tree. / These results enhance our understanding of H-free edge modification problems significantly. Our ideas and tools can be useful to future studies and may lead eventually to a dichotomy theorem on the existence of polynomial kernels for H-free edge modification problems. / Detailed summary in vernacular field only. / Cai, Yufei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 97-99). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter 1 --- Preliminaries --- p.1 / Chapter 1.1 --- Edge modification problems and kernelisation --- p.2 / Chapter 1.2 --- Main results --- p.4 / Chapter 1.3 --- The lack of polynomial kernels --- p.5 / Chapter 1.4 --- Conventions and organisation --- p.8 / Chapter 2 --- Component Design --- p.11 / Chapter 2.1 --- Weighted satisficability on selective formulas --- p.12 / Chapter 2.2 --- 4-cycle --- p.15 / Chapter 2.3 --- The general scheme of component design --- p.20 / Chapter 2.4 --- Applications --- p.26 / Chapter 3 --- Local Alteration --- p.31 / Chapter 3.1 --- Bigger forbidden subgraphs from smaller ones --- p.32 / Chapter 3.2 --- Lifting the quarantine --- p.37 / Chapter 4 --- Circuit Implementation --- p.43 / Chapter 4.1 --- Monotone circuits --- p.44 / Chapter 4.2 --- Centralisation --- p.45 / Chapter 4.3 --- Implementation --- p.48 / Chapter 5 --- Kernel for Diamond-Free Edge Deletion --- p.55 / Chapter 5.1 --- Diamond-graphs --- p.56 / Chapter 5.2 --- The invariant things --- p.59 / Chapter 5.3 --- Correctness --- p.61 / Chapter 5.4 --- Lockets --- p.64 / Chapter 5.5 --- Representative systems of diamonds --- p.68 / Chapter 5.6 --- Kernel size --- p.70 / Chapter 6 --- Conclusions --- p.73 / Chapter 6.1 --- 3-connected forbidden subgraphs --- p.74 / Chapter 6.2 --- Cycles, paths and nearly complete graphs --- p.76 / Chapter 6.3 --- Trees --- p.77 / Chapter 6.4 --- Open problems --- p.79 / Chapter A --- List of Trees --- p.81 / Chapter B --- List of Problems --- p.83 / Chapter C --- Glossary --- p.87 / Chapter D --- Bibliography --- p.96