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

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

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

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

${ Displaystyle G circ H: = (V, E)}$

куда

${ displaystyle V = left {(g_ {i}, h_ {j}): 1 leq i leq n, 1 leq j leq m right }}$

и

${ displaystyle 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 }}$

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

Приложения

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

Если ЧАС полный граф с двумя вершинами K₂, то для любого графа грамм, корневой продукт грамм и ЧАС имеет число господства ровно половина его вершин. Таким образом возникает любой связный граф, в котором число доминирования составляет половину числа вершин, за исключением четырехвершинного график цикла. Эти графики можно использовать для создания примеров, в которых граница Гипотеза Визинга, недоказанное неравенство между числом доминирования графов в другом графовом произведении, декартово произведение графиков, точно выполняется (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.