The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


"Counting Combinatorial Structures in Recursively Constructible Graphs"

By

Mr. Yiu-Cho Leung


Abstract

A sequence of graphs is recursively constructible if a graph in the
sequence can be easily constructed from its predecessor by a constant
number of simple operations. In this thesis, we focus on counting
different combinatorial structures in recursively constructible graphs,
and, in particular, grids,  toris and circulant graphs. Our goal is to
derive formulas in n (the number of vertices in the graph). The
combinatorial structures addressed include spanning trees, hamiltonian
cycles, directed cycle covers, independent sets, etc.

Such counting problems have been previously well-studied for the case of
grids. We first survey these results, codify the technique used, and then
show how to extend them to work on tori as well.

Circulant graphs do not, a-priori, seem to be recursively constructible.
We show that both constant and non-constant jump circulants are
recursively constructible. We then use this fact to count various
structures in both types of circulants.

Finally, we show that directed circulant graphs are recursively
constructible. This permits us to extend previously known techniques for
calculating the permanents of circulant matrices.


Date:			Monday, 30 July 2007

Time:			2:00p.m.-4:00p.m.

Venue:			Room 3501
			Lifts 25-26

Chairman:		Prof. Tai-Kai Ng (PHYS)

Committee Members:	Prof. Mordecai Golin (Supervisor)
			Prof. Siu-Wing Cheng
			Prof. Cunsheng Ding
			Prof. Beifang Chen (MATH)
			Prof. Felipe Cucker (Mathematics, CityU)


**** ALL are Welcome ****