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

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

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

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

Застосування

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

Якщо H — повний граф з двома вершинами K_2, то для будь-якого графу G кореневий добуток графів G і H має число домінування, рівне рівно половині числа його вершин. Будь-який зв'язний граф, у якому число домінування дорівнює половині вершин, виходить таким чином, за винятком циклу з чотирма вершинами. Ці графи можна використовувати для генерування прикладів, у яких для прямого добутку графів досягається границя з гіпотези Візінга, недоведеної нерівності між числом домінування графів у різних добутках графів.

Див. також

• Добуток графів

Література

• C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc.. — 1978. — Т. 18, вип. 1 (16 червня). — С. 21–28. — DOI:10.1017/S0004972700007760. Архівовано з джерела 5 лютого 2012. Процитовано 25 червня 2021.
• 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 (16 червня). — С. 287–293. — DOI:10.1007/BF01848079.
• K. M. Koh, D. G. Rogers, T. Tan. Products of graceful trees // Discrete Mathematics. — 1980. — Т. 31, вип. 3 (16 червня). — С. 279–292. — DOI:10.1016/0012-365X(80)90139-9.