Cayley digraphs of finite abelian groups and monomial ideals
View/ Open
Identificadores
URI: http://hdl.handle.net/10902/1634DOI: 10.1137/050646056
ISSN: 1095-7146
ISSN: 0895-4801
Full record
Show full item recordDate
2007Derechos
© 2007 Society for Industrial and Applied Mathematics
Publicado en
SIAM Journal on Discrete Mathematics, 2007, 21(3), 763–784
Publisher
Society for Industrial and Applied Mathematics
Palabras clave
Monomial ideals
Cayley digraph
Gröbner bases
Multiloop networks
Abstract:
In the study of double-loop computer networks, the diagrams known as L-shapes arise as a graphical representation of an optimal routing for every graph’s node. The description of these diagrams provides an efficient method for computing the diameter and the average minimum distance of the corresponding graphs. We extend these diagrams to multiloop computer networks. For each Cayley digraph with a finite abelian group as vertex set, we define a monomial ideal and consider its representations via its minimal system of generators or its irredundant irreducible decomposition. From this last piece of information, we can compute the graph’s diameter and average minimum distance. That monomial ideal is the initial ideal of a certain lattice with respect to a graded monomial ordering. This result permits the use of Gr¨obner bases for computing the ideal and finding an optimal routing. Finally, we present a family of Cayley digraphs parametrized by their diameter d, all of them associated to irreducible monomial ideals.
Collections to which it belong
- D20 Artículos [364]
- D21 Artículos [274]