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

В математической теории графов $корневое$ произведение графа G и корневого графа $H$ определяется следующим образом: возьми $|$ $В$ $($ $Г$ $)$ $|$ копий $H$ и для каждой вершины $vi$ $из$ $G$ отождествите vi $с$ $корневым$ узлом $i$ - й копии $H.$

Более формально, полагая, что

{\begin{aligned}V(G)&=\{g_{1},\ldots ,g_{n}\},\\V(H)&=\{h_{1},\ldots , h_{m}\},\end{aligned}}

и что корневой узел $H$ равен $h 1$ , определим

G\circ H:=(V,E)

где

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

E={\Bigl \{}{\bigl (}(g_{i},h_{1}),(g_{k},h_{1}){\bigr)}:(g_{i} ,g_{k})\in E(G){\Bigr \}}\cup \bigcup _{i=1}^{n}{\Bigl \{}{\bigl (}(g_{i},h_ {j}),(g_{i},h_{k}){\bigr )}:(h_{j},h_{k})\in E(H){\Bigr \}}

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

Приложения

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

Если $H$ — полный двухвершинный граф $K 2$ , то для любого графа $G$ корневое произведение $G$ и $H$ имеет число доминирования ровно половину от числа его вершин. Таким образом возникает каждый связный граф, в котором число доминирования равно половине числа вершин, за исключением четырехвершинного графа циклов . Эти графы можно использовать для создания примеров, в которых точно выполняется граница гипотезы Визинга , недоказанного неравенства между числом доминирования графов в другом графовом продукте, декартовом произведении графов (Fink et al. 1985). Это также хорошо покрытые графы .

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

Приложения

Рекомендации