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

В теории графов корневое произведение графа 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₁). Корневое произведение является подграфом прямого произведения тех же самых двух графов.

Приложения

Корневое произведение особенно актуально для деревьев, поскольку корневое произведение двух деревьев снова будет деревом. Например, Кох и др. (1980) использовали корневые произведения для поиска грациозной нумерации для широкого семейства деревьев.

Если H — полный граф с двумя вершинами K₂, то для любого графа G корневое произведение графов G и H имеет число доминирования, равное ровно половине числа его вершин. Любой связный граф, в котором число доминирования равно половине вершин, получается таким образом, за исключением цикла с четырьмя вершинами. Эти графы можно использовать для генерации примеров, в которых для прямого произведения графов достигается граница из гипотезы Визинга, недоказанного неравенства между числом доминирования графов в различных произведениях графов^[1].