Sung-Jin Cho ; Un-Sook Choi ; Han-Doo Kim ; Yoon-Hee Hwang ; Jin-Gyoung Kim - 60/102 Null Boundary Cellular Automata based expander graphs

dmtcs:2760 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS - https://doi.org/10.46298/dmtcs.2760
60/102 Null Boundary Cellular Automata based expander graphs

Authors: 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

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.


Volume: DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Expander graphs,60/102 NBCA,Spectral gaps,Bipartite graphs,Eigenvalue.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 171 times.
This article's PDF has been downloaded 341 times.