Some exact values for the diameter in Cayley graph Hl,p

• Caroline Patrão UFRJ
• Luis Kowada UFF
• Diane Castonguay UFG
• André Ribeiro IFGoiano
• Celina Figueiredo UFRJ

DOI: https://doi.org/10.5753/etc.2019.6395

Abstract

The family of graphs H,p has been defined in the context of edge partitions. The established properties such as vertex transitivity and low diameter suggest this family as a good topology for the design of interconnection networks. The vertices of the graphH p are the tuples with values between 0 and p1, such that the sum of the values is a multiple of p, and there is an edge between two vertices, if the two corresponding tuples have two pairs of entries whose values differ by one unit. In order to work towards the diameter, the difference between an upper and a lower bounds is established to be at most and we present subfamilies of graphs H p such that, for several values of and p, the bounds are tight.

Keywords: Cayley graph, diameter

References

Castonguay, D., Ribeiro, A. C., Figueiredo, C. M. H., and Kowada, L. A. B. (2015). On the diameter of the Cayley Graph H?,p. Matem´atica Contemporˆanea, 44:1–10.

Holyer, I. (1981). The NP−Completeness of Some Edge-Partition Problems. SIAM Journal Computing, 10(4):713–717.

Ribeiro, A. C., Figueiredo, C. M. H., and Kowada, L. A. B. (2010). An evidence for Lov´asz conjecture about Hamiltonian paths and cycles. Matem´atica Contemporˆanea, 39:121–128.

Vadapalli, P. and Srimani, P. K. (1996). A New Family of Cayley Graph Interconnection Networks of Constant Degree Four. IEEE Transactions on Parallel and Distributed Systems, 7(1):26–32.