60/102 Null Boundary Cellular Automata based expander graphs

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 expande...

Full description

Saved in:
Bibliographic Details
Main Authors: Cho, Sung-Jin, Choi, Un-Sook, Kim, Han-Doo, Hwang, Yoon-Hee, Kim, Jin-Gyoung
Format: Conference Proceeding
Language:English
Subjects:
Cellular Automata and Lattice Gases
Combinatorics
Computer Science
Discrete Mathematics
Dynamical Systems
Mathematics
Nonlinear Sciences
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.2760