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

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

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

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

[math]\displaystyle{ G \circ H := (V, E) }[/math],

где

[math]\displaystyle{ V = \left\{(g_i, h_j): 1\leq i\leq n, 1\leq j\leq m\right\} }[/math]

и

[math]\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\} }[/math]

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

Приложения

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

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

Литература

• C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc.. — 1978. — Т. 18, вып. 1. — С. 21–28. — doi:10.1017/S0004972700007760.
• J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts. On graphs having domination number half their order // Period. Math. Hungar.. — 1985. — Т. 16, вып. 4. — С. 287–293. — doi:10.1007/BF01848079.
• K. M. Koh, D. G. Rogers, T. Tan. Products of graceful trees // Discrete Mathematics. — 1980. — Т. 31, вып. 3. — С. 279–292. — doi:10.1016/0012-365X(80)90139-9.