Connectedness and isomorphism properties of the zig-zag product of graphs

DOI10.1002/JGT.21917zbMATH Open1346.05244arXiv1404.4342OpenAlexW1877125464MaRDI QIDQ2825486FDOQ2825486

Authors: Daniele D'Angeli, Alfredo Donno, Ecaterina Sava 

Publication date: 13 October 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: In this paper we investigate the connectedness and the isomorphism problems for zig-zag products of two graphs. A sufficient condition for the zig-zag product of two graphs to be connected is provided, reducing to the study of the connectedness property of a new graph which depends only on the second factor of the graph product. We show that, when the second factor is a cycle graph, the study of the isomorphism problem for the zig-zag product is equivalent to the study of the same problem for the associated pseudo-replacement graph. The latter is defined in a natural way, by a construction generalizing the classical replacement product, and its degree is smaller than the degree of the zig-zag product graph. Two particular classes of products are studied in detail: the zig-zag product of a complete graph with a cycle graph, and the zig-zag product of a $4$-regular graph with the cycle graph of length $4$. Furthermore, an example coming from the theory of Schreier graphs associated with the action of self-similar groups is also considered: the graph products are completely determined and their spectral analysis is developed.

Full work available at URL: https://arxiv.org/abs/1404.4342

Recommendations

• scientific article; zbMATH DE number 6315655
• Cayley graphs isomorphic to the product of two Cayley graphs.
• A generalization of the zig-zag graph product by means of the sandwich product
• Self-similar groups and the zig-zag and replacement products of graphs
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product

zbMATH Keywords

connected componentzig-zag productreplacement productdouble cycle graphparity blockparity block decompositionpseudo-replacement

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Eigenvectors of block circulant and alternating circulant matrices
• Filling Riemannian manifolds
• Expander graphs in pure and applied mathematics
• Expander graphs and their applications
• The Tutte polynomial of the Sierpiński and Hanoi graphs
• Amenability via random walks.
• Generalized wreath products of graphs and groups
• Title not available (Why is that?)
• Schreier graphs of the Basilica group.
• ON A TORSION-FREE WEAKLY BRANCH GROUP DEFINED BY A THREE STATE AUTOMATON
• Counting dimer coverings on self-similar Schreier graphs
• Partition functions of the Ising model on some self-similar Schreier graphs
• Zig-zag and replacement product graphs and LDPC codes
• On one-factorizations of replacement products

Cited In (4)

• Zeta functions of finite Schreier graphs and their zig-zag products
• Permutational powers of a graph
• Some degree and distance-based invariants of wreath products of graphs
• A generalization of the zig-zag graph product by means of the sandwich product

This page was built for publication: Connectedness and isomorphism properties of the zig-zag product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2825486)