PhD Thesis Proposal Defence


"Counting the number of spanning trees in graphs"

By

Mr. Yuanping Zhang


Abstract

As being combinatorial interesting and application uses, the number
of spanning trees in a (di-)graph (network) is an important, well-studied
quantity. Most of research about the number of spanning trees is devoted
to determining exact formulae for the number of spanning trees in many
kinds of special graphs.

In this proposal, we state the general methods for counting the number of
spanning trees in (di-)graphs first. Then we talk about some our new
results. We show that, the number of spanning trees in the circulant graph
$C_n^{s_1,s_2,\cdots, s_k}$ always satisfies a recurrence relation and
describe how to derive the relation. The asymptotic behavior of these
quantities are derived also. Boesch and Prodinger have shown how to use
Chebyshev polynomials to derive closed formulae for the number of spanning
trees of graphs in certain classes. This work has been extended to develop
new technique for the evaluation of the number of spanning trees in
circulant graphs. Then, we describe a method to count the number of
spanning trees in one class of double fixed-step loop networks. We propose
some possible future works at last.


Date:				Wednesday, 27 March 2002

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

Venue:				Room 3301
				Lifts 17-18

Committee Members:		Dr. Mordecai Golin (Supervisor)
				Dr. Rudolf Fleischer (Chairman)
				Dr. Sunil Arya
				Dr. Siu-Wing Cheng


**** ALL are Welcome ****