Корневое произведение

В теории графов корневое произведение графа G и корневого графа H определяется следующим образом: возьмём |V(G)| копий графа H и для каждой вершины ${\displaystyle v_{i}}$ графа G, отождествляем ${\displaystyle v_{i}}$ с корневой вершиной i-ой копии H.

Корневое произведение графов.

Более формально. Предположим, что V(G) = {g₁, ..., g_n}, V(H) = {h₁, ..., h_m} и что корнем графа H является ${\displaystyle h_{1}}$. Определим произведение

${\displaystyle G\circ H:=(V,E)}$,

где

${\displaystyle V=\left\{(g_{i},h_{j}):1\leq i\leq n,1\leq j\leq m\right\}}$

и

${\displaystyle E=\left\{((g_{i},h_{1}),(g_{k},h_{1})):(g_{i},g_{k})\in E(G)\right\}\cup \bigcup _{i=1}^{n}\left\{((g_{i},h_{j}),(g_{i},h_{k})):(h_{j},h_{k})\in E(H)\right\}}$

Если граф G является также корневым с корнем g₁, можно рассматривать произведение само как корневой граф с корнем (g₁, h₁). Корневое произведение является подграфом прямого произведения тех же самых двух графов.