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

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

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

Примеры [ править ]

Например, двудольная половина полного двудольного графа K _{n , n} - это полный граф K _n, а двудольная половина графа гиперкуба - это разрезанный пополам граф куба . Когда G - дистанционно регулярный граф , обе его двудольные половины дистанционно регулярны. ^[2] Например, разрезанный пополам граф Фостера является одним из конечного числа дистанционно регулярных локально линейных графов шестой степени . ^[3]

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

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

Особые случаи [ править ]

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

См. Также [ править ]

Двусторонняя двойная обложка

Ссылки [ править ]

^ Уилсон, Робин Дж. (2004), Разделы алгебраической теории графов , Энциклопедия математики и ее приложений, 102 , Cambridge University Press, стр. 188, ISBN 9780521801973.
^ Чихара, Лаура; Stanton, Dennis (1986), "схема ассоциации и квадратичные преобразования для ортогональных многочленов", Графы и комбинаторика , 2 (2): 101-112, DOI : 10.1007 / BF01788084 , MR 0932118 , S2CID 28803214 .
^ Хираки, Akira; Номура, Казумаса; Сузуки, Хироши (2000), "Расстояние-регулярные графы валентности 6 и ", Журнал алгебраической комбинаторике , 11 (2): 101-134, DOI : 10,1023 / A: 1008776031839 , МР 1761910 ${\ displaystyle a_ {1} = 1}$
^ Le, Хоанг-Oanh; Ле, Ван Банг (2019), «Ограниченные представления графов карт и полуквадратов», Россманит, Питер; Хеггернес, Пинар; Катоен, Йост-Питер (ред.), 44-й Международный симпозиум по математическим основам информатики, MFCS 2019, 26-30 августа 2019 г., Ахен, Германия , LIPIcs, 138 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. : 1-13: 15, DOI : 10,4230 / LIPIcs.MFCS.2019.13
^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, Проблема GT59.
^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Графики карт», Журнал ACM , 49 (2): 127–138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819 , S2CID 2657838 .

[1] Уилсон, Робин Дж. (2004), Разделы алгебраической теории графов , Энциклопедия математики и ее приложений, 102 , Cambridge University Press, стр. 188, ISBN 9780521801973.

[2] Чихара, Лаура; Stanton, Dennis (1986), "схема ассоциации и квадратичные преобразования для ортогональных многочленов", Графы и комбинаторика , 2 (2): 101-112, DOI : 10.1007 / BF01788084 , MR 0932118 , S2CID 28803214 .

[3] Хираки, Akira; Номура, Казумаса; Сузуки, Хироши (2000), "Расстояние-регулярные графы валентности 6 и ", Журнал алгебраической комбинаторике , 11 (2): 101-134, DOI : 10,1023 / A: 1008776031839 , МР 1761910 ${\ displaystyle a_ {1} = 1}$

[4] Le, Хоанг-Oanh; Ле, Ван Банг (2019), «Ограниченные представления графов карт и полуквадратов», Россманит, Питер; Хеггернес, Пинар; Катоен, Йост-Питер (ред.), 44-й Международный симпозиум по математическим основам информатики, MFCS 2019, 26-30 августа 2019 г., Ахен, Германия , LIPIcs, 138 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. : 1-13: 15, DOI : 10,4230 / LIPIcs.MFCS.2019.13

[5] Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, Проблема GT59.

[6] Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Графики карт», Журнал ACM , 49 (2): 127–138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819 , S2CID 2657838 .

[1]