Unhooking Circulant Graphs
Leung Yiu Cho
HKUST
Friday, March 26, 2004.
11-12, room 3464



Abstract
It has long been known that the number of spanning trees in
circulant graphs with fixed jumps and n nodes satisfies a
recurrence relation in n. The proof of this fact was algebraic
and not combinatorial. In this talk, a straightforward combinatorial
proof of this fact will be given. Instead of trying to decompose
a large circulant graph into smaller ones, our technique is to
instead decompose a large circulant graph into different line
graph cases and then construct a recurrence relation on the
line graphs. We then generalize this technique to show that the
numbers of Hamiltonian Cycles, Eulerian Cycles and Eulerian
Orientations in circulant graphs also satisfy recurrence relations.