2007/03/26 by Shunichi Nomura, Nomura, Shunichi, Akimichi Takemura +1
Computer Science · Mathematics · #60J10 #68R10 #Advanced Graph Theory Research #Cellular Automata and Applications #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #math.PR #msc:60J10 #msc:68R10
paper · pdf · doi:10.48550/arxiv.math/0703742
arxiv created 2007/03/26 · openalex publication_date 2007/03/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a generalization of the zig-zag product of regular digraphs (directed graphs), which allows us to construct regular digraphs with m ore flexible choices of the degrees. In our generalization, we can control the connectivity of the resulting graph measured by its spectral expansion. We derive an upper bound on the spectral expansion of the generalized zig-zag product. Our upper bound improves on known bounds when applied to the zig-zag product. We also consider a special case of the generalized zig-zag product, where one of the components is a trivial graph whose edges are all self-loops. We call it a reduced zig-zag product and derive a bound on the spectral expansion of its powers.