PhD Thesis Proposal Defence


"Counting Combinatorial Structures in Circulant Graphs"

by

Mr. Yiu Cho Leung


Abstract:

Circulants graphs are a well-studied subclass of regular graphs,
partially because they model many practical computer network
topologies. In this proposal, we focus on counting  different
combinatorial structures in circulant graphs with constant jumps
and  non-constant jumps. Our goal is to derive counting formulas
in 'n' (the number of vertices). The combinatorial structures
addressed include Spanning trees, Hamiltonian cycles, directed
cycle covers and more.

It was known that the number of spanning trees in constant-jump
circulant graphs satisfy recurrences relation with constant coefficients.
The proofs were algebraic in structure and only worked for constant
jump circulants and only for spanning trees. In this proposal we
discuss general combinatorial techniques for counting different types
of structures in circulants,  both with constant and non-constant jumps.
We will also extend our approach of counting to count structures in
grid graphs and tori.


Date:     		Friday, 1 December 2006

Time:                   3:00p.m.-5:00p.m.

Venue:                  Room 4480
			lifts 25-26

Committee Members:      Dr. Mordecai Golin (Supervisor)
                        Dr. Cunsheng Ding (Chairperson)
			Dr. Sunil Arya
			Dr. Siu Wing Cheng


**** ALL are Welcome ****