60/102 Null Boundary Cellular Automata based expander graphs
Sung-Jin Cho (1), Un-Sook Choi (2), Han-Doo Kim (3), Yoon-Hee Hwang (1), Jin-Gyoung Kim (1)
(1) Department of Applied Mathematics
(2) Department of Media Engineering
(3) School of Computer Aided Science
Abstract
Expander graphs are useful in the design and analysis of communication networks. Mukhopadhyay et al. introduced a method to generate a family of expander graphs based on nongroup two predecessor single attractor Cellular Automata(CA). In this paper we propose a method to generate a family of expander graphs based on 60/102 Null Boundary CA(NBCA) which is a group CA. The spectral gap generated by our method is maximal. Moreover, the spectral gap is larger than that of Mukhopadhyay et al.
