WikiDer > Двудольная половина

Bipartite half
Разделенный пополам куб-граф порядка 4, полученный как двудольная половина графа-гиперкуба порядка 4

В теория графов, то двудольная половина или же полуквадрат из двудольный граф грамм = (U,V,E) - граф, множество вершин которого является одной из двух сторон двудольного (не теряя общий смысл, U) и в котором есть ребро тыятыj для каждых двух вершин тыя и тыj в U которые находятся на расстоянии двух друг от друга в грамм.[1] То есть, в более компактных обозначениях, двудольная половина равна грамм2[U], где верхний индекс 2 означает квадрат графика а квадратные скобки обозначают индуцированный подграф.

Например, двудольная половина полный двудольный граф Kп,п это полный график Kп и двудольная половина граф гиперкуба это вдвое кубический граф.Когда грамм это дистанционно регулярный граф, его две двудольные половины дистанционно регулярны.[2] Например, половину Граф Фостера является одним из конечного числа дистанционно регулярных степеней 6 локально линейные графы.[3]

В карты графиков, это графы пересечений внутренних непересекающихся односвязных областей на плоскости, являются в точности двудольными половинами двудольных планарные графы.[4]

Смотрите также

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

  1. ^ Уилсон, Робин Дж. (2004), Темы по алгебраической теории графов, Энциклопедия математики и ее приложений, 102, Cambridge University Press, стр. 188, ISBN 9780521801973.
  2. ^ Чихара, Лаура; Стэнтон, Деннис (1986), "Схемы ассоциации и квадратичные преобразования для ортогональных многочленов", Графы и комбинаторика, 2 (2): 101–112, Дои:10.1007 / BF01788084, МИСТЕР 0932118.
  3. ^ Хираки, Акира; Номура, Казумаса; Судзуки, Хироши (2000), "Дистанционно регулярные графы валентности 6 и ", Журнал алгебраической комбинаторики, 11 (2): 101–134, Дои:10.1023 / А: 1008776031839, МИСТЕР 1761910
  4. ^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карты-графики», Журнал ACM, 49 (2): 127–138, arXiv:cs / 9910013, Дои:10.1145/506147.506148, МИСТЕР 2147819.