In
graph theory, the replacement product of two graphs is a
graph product that can be used to reduce the
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
of a graph while maintaining its
connectivity.
Suppose ''G'' is a ''d''-
regular graph and ''H'' is an ''e''-regular graph with vertex set . Let ''R'' denote the replacement product of ''G'' and ''H''. The vertex set of ''R'' is the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
''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 ''i''th neighbor of ''u'' and ''u'' is the ''j''th 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
External links
*
Graph products
{{Combin-stub