On the diameter of the Cayley Graph Hl,p
Carregando...
Data
2015
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
The family H`;p has been de ned in the context of edge parti-
tions. Subsequently, it was shown to be composed of Hamiltonian
Cayley graphs, and that it is possible to determine the diameter of
H`;p in O(`) time. The established properties such as the low di-
ameter suggest the H`;p graph as a good topology for the design of
interconnection networks. The p`1 vertices of the graph H`;p are
the `-tuples with values between 0 and p 1, such that the sum of
the ` values is a multiple of p, and there is an edge between two ver-
tices if the two corresponding tuples have two pairs of entries whose
values di er by one unit. Our goal is to nd the diameter of Cayley
graph H`;p in time O(log(`+p)). In this work, we did this for some
families of graphs. We also show that the diameter of H`;p is the
same of Hp;`. Finally, we nd a tight upper bound on the diameter
of H`;p.
Descrição
Palavras-chave
Interconnection networks, Cayley graphs, Diameter and graphs Hl,p
Citação
CASTONGUAY, Daine; RIBEIRO, André da C.; KOWADA, Luis Antonio B.; FIGUEIREDO, Celina M. H. de. On the diameter of the Cayley Graph Hl,p. Matemática Contemporânea, Rio de Janeiro, v. 44, p. 1-10, 2015.