In graph theory, the replacement product of two graphs is a graph product that can be used to reduce the degree of a graph while maintaining its connectivity. [1]
Suppose G is a d- regular graph and H is an e-regular graph with vertex set {0, …, d – 1}. Let R denote the replacement product of G and H. The vertex set of R is the Cartesian product V(G) × V(H). For each vertex u in V(G) and for each edge (i, j) in E(H), the vertex (u, i) is adjacent to (u, j) in R. Furthermore, for each edge (u, v) in E(G), if v is the ith neighbor of u and u is the jth neighbor of v, the vertex (u, i) is adjacent to (v, j) in R.
If H is an e-regular graph, then R is an (e + 1)-regular graph.
References
- ^ Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 August 2006). "Expander graphs and their applications". Bulletin of the American Mathematical Society. 43 (4): 439–562. doi: 10.1090/S0273-0979-06-01126-8.
External links
- Trevisan, Luca (7 March 2011). "CS359G Lecture 17: The Zig-Zag Product". Retrieved 16 December 2014.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |
In graph theory, the replacement product of two graphs is a graph product that can be used to reduce the degree of a graph while maintaining its connectivity. [1]
Suppose G is a d- regular graph and H is an e-regular graph with vertex set {0, …, d – 1}. Let R denote the replacement product of G and H. The vertex set of R is the Cartesian product V(G) × V(H). For each vertex u in V(G) and for each edge (i, j) in E(H), the vertex (u, i) is adjacent to (u, j) in R. Furthermore, for each edge (u, v) in E(G), if v is the ith neighbor of u and u is the jth neighbor of v, the vertex (u, i) is adjacent to (v, j) in R.
If H is an e-regular graph, then R is an (e + 1)-regular graph.
References
- ^ Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 August 2006). "Expander graphs and their applications". Bulletin of the American Mathematical Society. 43 (4): 439–562. doi: 10.1090/S0273-0979-06-01126-8.
External links
- Trevisan, Luca (7 March 2011). "CS359G Lecture 17: The Zig-Zag Product". Retrieved 16 December 2014.
|
| This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |