Counting Structures in Non-Constant-Jump Circulant Graphs.
Wang Yajun
HKUST





Date: Friday October 8, 2004
Time 11-12
Venue: 3464


Abstract
Circulant graphs are an extremely well-studied subclass of
regular graphs,  partially because they model many practical computer
network topologies. It has long been known that the number of spanning trees 
in n-node circulant graphs  with  constant jumps satisfies a
recurrence relation in n.  For the non-constant-jump case, i.e., 
where some  jump sizes can be functions of the graph size,  only a few
special cases such as the Mobius ladder had been studied but no 
general results  were known.

In this  talk we show how that the number of spanning trees for  all
classes of n node circulant graphs satisfies a recurrence relation
in n  even when the  jumps are non-constant (but linear) in the graph size. 
The technique developed is
very general and can be used to show that many other structures  of these
circulant graphs, e.g., number of Hamiltonian Cycles, Eulerian Cycles, 
Eulerian Orientations, etc., also satisfy recurrence relations. 

The technique presented for deriving the recurrence
relations  is very mechanical and,  for circulant graphs
with small jump parameters, can easily be quickly implemented on a computer.
We illustrate this by deriving recurrence relations counting
all of the structures listed above for various 
circulant graphs.

This is joint work with Leung Yiu Cho and Mordecai Golin