graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the replacement product of two graphs is a

graph product In graph theory, a graph product is a binary operation on Graph (discrete mathematics), graphs. Specifically, it is an operation that takes two graphs and and produces a graph with the following properties: * The vertex (graph theory), vertex ...

that can be used to reduce the degree of a graph while maintaining its

connectivity Connectivity may refer to: Computing and technology * Connectivity (media), the ability of the social media to accumulate economic capital from the users connections and activities * Internet connectivity, the means by which individual terminal ...

. Suppose ''G'' is a ''d''-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...

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 ''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