Use este identificador para citar ou linkar para este item: http://repositorio.bc.ufg.br/handle/ri/19277
Tipo do documento: Artigo
Título: On the diameter of the Cayley Graph Hl,p
Autor: Castonguay, Diane
Ribeiro, André da Cunha
Kowada, Luis Antonio Brasil
Figueiredo, Celina Miraglia Herrera de
Abstract: 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.
Palavras-chave: Interconnection networks
Cayley graphs
Diameter and graphs Hl,p
País: Brasil
Unidade acadêmica: Instituto de Informática - INF (RG)
Programa: Programa de Pós-graduação em Ciência da Computação em Rede
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.
Tipo de acesso: Acesso Aberto
Attribution-NonCommercial-NoDerivatives 4.0 International
Endereço da licença: http://creativecommons.org/licenses/by-nc-nd/4.0/
URI: http://repositorio.bc.ufg.br/handle/ri/19277
Data de publicação: 2015
Aparece nas coleções:INF - Artigos publicados em periódicos

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Artigo - Diane Castonguay - 2015.pdf268,94 kBAdobe PDFThumbnail
Baixar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons