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

В математической теории графов корневое произведение графа 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 ). Это также хорошо покрытые графы .

Ссылки

Годсил, CD ; Маккей, Б.Д. (1978), «Новый графовый продукт и его спектр» (PDF) , Bull. Австрал. Математика. Соц. , 18 (1): 21–28, doi : 10.1017/S0004972700007760 , MR 0494910 .
Финк, Дж. Ф.; Джейкобсон, MS; Кинч, Л.Ф.; Робертс, Дж. (1985), «О графах, имеющих доминирование половины их порядка», Период. Математика. Венгрия. , 16 (4): 287–293, doi : 10.1007/BF01848079 , MR 0833264 .
Кох, КМ; Роджерс, генеральный директор; Тан, Т. (1980), «Произведения изящных деревьев», Дискретная математика , 31 (3): 279–292, doi : 10.1016/0012-365X(80)90139-9 , MR 0584121 .