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

В теории графов корневое произведение графа 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.