Connectedness and isomorphism properties of the zig-zag product of graphs
From MaRDI portal
Publication:2825486
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 -regular graph with the cycle graph of length . 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.
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
Cites work
- scientific article; zbMATH DE number 6315655 (Why is no real title available?)
- Amenability via random walks.
- Counting dimer coverings on self-similar Schreier graphs
- Eigenvectors of block circulant and alternating circulant matrices
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Expander graphs and their applications
- Expander graphs in pure and applied mathematics
- Filling Riemannian manifolds
- Generalized wreath products of graphs and groups
- ON A TORSION-FREE WEAKLY BRANCH GROUP DEFINED BY A THREE STATE AUTOMATON
- On one-factorizations of replacement products
- Partition functions of the Ising model on some self-similar Schreier graphs
- Schreier graphs of the Basilica group.
- The Tutte polynomial of the Sierpiński and Hanoi graphs
- Zig-zag and replacement product graphs and LDPC codes
Cited in
(4)
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)