У теорії графів кореневий добуток графу G і кореневого графу H визначається так візьмемо V G копій графу H і для кожної

У теорії графів кореневий добуток графу 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 має число домінування, рівне рівно половині числа його вершин. Будь-який зв'язний граф, у якому число домінування дорівнює половині вершин, виходить таким чином, за винятком циклу з чотирма вершинами. Ці графи можна використовувати для генерування прикладів, у яких для прямого добутку графів досягається границя з , недоведеної нерівності між числом домінування графів у різних добутках графів.

Див. також

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

Примітки

Fink, Jacobson, Kinch, Roberts, 1985.

Література

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 // . — 1980. — Т. 31, вип. 3 (16 червня). — С. 279–292. — DOI:10.1016/0012-365X(80)90139-9.

[FOOTNOTEFink,_Jacobson,_Kinch,_Roberts1985-1] Fink, Jacobson, Kinch, Roberts, 1985.