stringtranslate.com

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

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

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

Примеры

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

Представление и твердость

Каждый граф G является двудольной половиной другого графа, образованной путем деления ребер графа G на двудольные пути. В более общем смысле, представление графа G в виде двудольной половины можно найти, взяв любое кликовое покрытие ребер графа G и заменив каждую клику звездой . [ 4] Каждое представление возникает таким образом. Поскольку нахождение наименьшего кликового покрытия ребер является NP-трудной задачей, то и нахождение графа с наименьшим количеством вершин, для которого граф G является двудольной половиной, является NP-трудным. [5]

Особые случаи

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

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

Ссылки

  1. ^ Уилсон, Робин Дж. (2004), Темы алгебраической теории графов, Энциклопедия математики и ее приложений, т. 102, Cambridge University Press, стр. 188, ISBN 9780521801973.
  2. ^ Чихара, Лора; Стэнтон, Деннис (1986), «Схемы ассоциации и квадратичные преобразования для ортогональных многочленов», Графы и комбинаторика , 2 (2): 101–112, doi :10.1007/BF01788084, MR  0932118, S2CID  28803214.
  3. ^ Хираки, Акира; Номура, Казумаса; Судзуки, Хироси (2000), «Дистанционно-регулярные графы валентности 6 и », Журнал алгебраической комбинаторики , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR  1761910
  4. ^ Ле, Хоанг-Оан; Ле, Ван Банг (2019), «Ограниченные представления графов карт и полуквадратов», Россманит, Питер; Хеггернес, Пинар; Катоен, Йост-Питер (ред.), 44-й Международный симпозиум по математическим основам информатики, MFCS 2019, 26–30 августа 2019 г., Ахен, Германия , LIPIcs, vol. 138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 13: 1–13: 15, doi : 10.4230/LIPIcs.MFCS.2019.13 , ISBN 9783959771177
  5. ^ Гэри, Майкл Р.; Джонсон , Дэвид С. (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR  0519066. OCLC  247570676., Проблема GT59.
  6. ^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карты графиков», Журнал ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi : 10.1145/506147.506148, MR  2147819, S2CID  2657838.