Кореневий добуток

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

Кореневий добуток графів

Формальніше, припустимо, що V(G) = {g_1, ..., g_n}_, V(H) = {h_1, ..., 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_1, добуток можна розглядати як кореневий граф з коренем (g_1, h₁)_. Кореневий добуток є підграфом прямого добутку тих самих двох графів.