Name
Abstract | ||
|---|---|---|
In this article, 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. (C) 2015Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/jgt.21917 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
zig-zag product,replacement product,parity block,parity block decomposition,connected component,pseudo-replacement,double cycle graph | Topology,Discrete mathematics,Combinatorics,Line graph,Graph isomorphism,Graph property,Graph homomorphism,Graph product,Symmetric graph,Mathematics,Voltage graph,Replacement product | Journal |
Volume | Issue | ISSN |
83 | 2 | 0364-9024 |
Citations | PageRank | References |
1 | 0.38 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniele Dangeli | 1 | 3 | 1.24 |
| Alfredo Donno | 2 | 27 | 8.03 |
| ecaterina savahuss | 3 | 1 | 0.38 |