Title: Department of Computer Science Seminar
Date: Thursday, November 13, 2003
Time: 2:00 pm to 3:00pm
Venue: Room N101, CSIT Building [108]
       
Speaker:  Joan Gimbert

Title: Weak Distance-Regularity of Moore-Type Digraphs
       

Abstract:

The notion of distance-regularity for undirected graphs can be
`extended' for the directed case in two different ways. Damerell
adopted the strongest definition of distance-regularity, which is
equivalent to saying that the corresponding set of distance matrices
A_i_{i=0}^D constitutes a commutative association
scheme. In particular, a (strongly) distance-regular digraph Gamma
is stable, which means that A_i^{\top}=A_{g-i},
for each i=1,..,g-1, where g denotes the girth of Gamma. If
we remove the stability property from the definition of
distance-regularity, it still holds that the number of walks of a
given length between any two vertices of Gamma does not depend on
the chosen vertices but only on their distance. We consider the class
of digraphs characterized by such a weaker condition, referred to as
weakly distance-regular digraphs, and show that their spectrum
can also be obtained from a smaller `quotient digraph'. As happens in
the case of distance-regular graphs, the study is greatly facilitated
by a family of orthogonal polynomials called the distance polynomials.

We prove that Moore digraphs, and some other classes of extremal
digraphs, are weakly distance-regular. Then, as an application of the
developed theory, we give an alternative and unified proof of the
existence results on Moore digraphs, Moore bipartite digraphs and,
more generally, Moore generalized p-cycles. In addition, we show
that the line digraph structure appears as a characteristic property
of any Moore generalized $p$-cycle of diameter D >= 2p.

This is a joint work with Francesc Comellas, Miguel Angel Fiol and
Margarida Mitjana.


Biography:

Joan is visiting from the Departament de Matematica, Universitat de
Lleida Catalunya, Spain.


URL: 


Further Information: contact Ian Wanless, Ian.Wanless[at]cs.anu.edu.au

URL: http://cs.anu.edu.au/lib/seminars/seminars03/dept20031113a