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


PhD Thesis Defence


"Counting the number of spanning trees in special graphs"

By

Mr. Yuanping Zhang


Abstract

The number of spanning trees in a (di-)graph (network) is an important,
well-studied quantity, both for application reasons as well as being of
separate  combinatorial interest. Most research in this area is devoted to
determining exact formulae for the number of spanning trees in particular
classes of special graphs.

In this thesis, we start by describing known general methods for counting
the number of spanning trees in (di-) graphs. We then discuss our new
results: we start by showing that the number of spanning trees in the
circulant graph Cns1,s2,K, sk always satisfies a recurrence relation in n
and describe how to derive this relation. The asymptotic behavior of these
quantities is also derived.

We then extend results due to Boesch and Prodinger to derive closed
formulae for the number of spanning trees in circulant graphs and graphs
related to circulant graphs in terms of Chebyshev polynomials.

We conclude by describing a method of counting the number of spanning
trees in one class of double fixed-step loop networks.


Date:			Friday, 2 August 2002

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

Venue:			Room 2302
			Lifts 17-18

Chairman:		Dr. Kin-Yin Li (MATH)

Committee Members:	Dr. Mordecai Golin (Supervisor)
			Dr. Sunil Arya
			Prof. William Steiger
			Dr. Beifang Chen (MATH)
			Prof. Helmut Prodinger (Mathematics, Wits Univ.)


**** ALL are Welcome ****