Корневое произведение (Tkjuyfky hjkn[fy;yuny)

Перейти к навигации Перейти к поиску
Корневое произведение графов.

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

Более формально. Предположим, что V(G) = {g1, ..., gn}, V(H) = {h1, ..., hm} и что корнем графа H является . Определим произведение

,

где

и

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

Приложения

[править | править код]

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

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

Примечания

[править | править код]

Литература

[править | править код]
  • 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.