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.
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.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 120 |
Seitenumfang | 151 |
Fachzeitschrift | Journal of Graph Theory |
Jahrgang | 83 |
Ausgabenummer | 2 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2016 |
Fields of Expertise
- Information, Communication & Computing
Treatment code (Nähere Zuordnung)
- Theoretical