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

Rooted product of graphs
Корневое произведение графов.

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

Более формально, если предположить, что V(грамм) = {грамм1, ..., граммп}, V(ЧАС) = {час1, ..., часм} и что корневой узел ЧАС является , определять

куда

и

Если грамм также укоренен в грамм1, сам продукт можно увидеть как внедренный, по адресу (грамм1, час1). Корневой продукт - это подграф из декартово произведение тех же двух графиков.

Приложения

Продукт с укоренением особенно актуален для деревья, поскольку корневой продукт двух деревьев - это другое дерево. Например, Koh et al. (1980) использовали корневые продукты, чтобы найти изящная нумерация для широкого семейства деревьев.

Если ЧАС полный граф с двумя вершинами K2, то для любого графа грамм, корневой продукт грамм и ЧАС имеет число господства ровно половина его вершин. Таким образом возникает любой связный граф, в котором число доминирования составляет половину числа вершин, за исключением четырехвершинного график цикла. Эти графики можно использовать для создания примеров, в которых граница Гипотеза Визинга, недоказанное неравенство между числом доминирования графов в другом графовом произведении, декартово произведение графиков, точно выполняется (Fink et al. 1985 г.). Они также хорошо покрытые графики.

Рекомендации

  • Годсил, К. Д.; Маккей, Б.Д. (1978), «Новый графический продукт и его спектр» (PDF), Бык. Austral. Математика. Soc., 18 (1): 21–28, Дои:10.1017 / S0004972700007760, МИСТЕР 0494910.
  • Fink, J. F .; Jacobson, M. S .; Кинч, Л. Ф .; Робертс, Дж. (1985), "О графах с числом доминирования половину их порядка", Период. Математика. Hungar., 16 (4): 287–293, Дои:10.1007 / BF01848079, МИСТЕР 0833264.
  • Koh, K. M .; Роджерс, Д.Г .; Тан, Т. (1980), "Продукты изящных деревьев", Дискретная математика, 31 (3): 279–292, Дои:10.1016 / 0012-365X (80) 90139-9, МИСТЕР 0584121.