Symbolic Computation Group

Circulant digraphs are the Cayley digraphs of cyclic groups. While the description of a general directed graph of N vertices needs N2 bits, one can determine a circulant digraph with r*log(N) bits. This compact representation motivates the study of these objects.

Wong and Coppersmith (1974) introduced the concept of L-shape to represent in a Minimum Distance Diagram an optimal path joining each pair of vertices in a digraph of degree two. In this talk we will see how monomial ideals are a natural way to extend this representation to digraphs of arbitrary degree.

Using Groebner Bases, we can give a description of these Minimum Distance Diagrams and obtain some graph's parameters, as its diameter and average distance.