Симплексный граф

В теории графов , разделе математики , симплекс-граф $κ(G)$ неориентированного графа $G$ сам по себе является графом с одним узлом для каждой клики (набора взаимно смежных вершин) $G.$ в Два узла $κ(G)$ соединяются ребром всякий раз, когда соответствующие две клики различаются наличием или отсутствием одной вершины.

Пустой набор включается как одна из клик $G$ , которые используются для формирования графа клик, как и каждый набор из одной вершины и каждый набор из двух соседних вершин. Следовательно, симплексный граф содержит в подразделение самой $G.$ себе Симплексный граф полного графа является графом гиперкуба , а симплексный граф графа циклов длины четыре или более является графом передач . Симплексный граф графа дополнений графа путей представляет собой куб Фибоначчи .

Полным подграфам $G$ можно придать структуру медианной алгебры : медиана трех клик $A$ , $B$ и $C$ образована вершинами, принадлежащими большинству трех клик. ^[1] Любые две вершины, принадлежащие этому медианному множеству, должны принадлежать хотя бы одному из $A$ , $B$ или $C$ и, следовательно, должны быть связаны ребром, поэтому медиана трех клик сама по себе является кликой. Симплексный граф — это медианный граф, соответствующий этой структуре медианной алгебры. Когда $G$ является графом дополнений , двудольного графа кликам $G$ можно придать более сильную структуру в виде дистрибутивной решетки , ^[2] и в этом случае граф симплекса является графиком решетки. Как и в более общем случае с медианными графами, каждый симплексный граф сам по себе является двудольным .

Граф симплексов имеет одну вершину для каждого симплекса в комплексе клики $X (G)$ графа $G$ , и две вершины связаны ребром, когда один из двух соответствующих симплексов является фасетом другого. Таким образом, объекты (вершины в симплекс-графе, симплексы в $X (G)$ ) и отношения между объектами (ребра в симплекс-графе, отношения включения между симплексами в $X (G)$ ) находятся во взаимно однозначном соответствии между $X (г)$ и $κ(г)$ .

Симплексные графы были представлены Бандельтом и ван де Велем (1989) . ^[3] который заметил, что симплексный граф не имеет кубов тогда и только тогда, когда базовый граф не содержит треугольников , и показал, что хроматическое число базового графа равно минимальному числу $n,$ такому что симплексный граф может быть изометрически вложен в декартово произведение $н$ деревья. Вследствие существования графов без треугольников с высоким хроматическим числом они показали, что существуют двумерные топологические медианные алгебры , которые не могут быть вложены в произведения конечного числа вещественных деревьев . Имрих, Клавжар и Малдер (1999) также используют симплекс-графы как часть своего доказательства того, что проверка того, является ли граф свободным от треугольников или является ли он медианным графом, может быть выполнена одинаково быстро.

Примечания

^ Бартелеми, Леклерк и Монжарде (1986) , стр. 200.
^ Пропп (1997) .
^ Имрих, Клавжар и Малдер (1999) приписывают введение симплексных графов более поздней статье, также Бандельту и ван де Велю, но это кажется ошибкой.

Ссылки

Бандельт, Х.-Ю.; Чепой, В. (2008), «Метрическая теория графов и геометрия: обзор», в Гудмане, Дж. Э .; Пах, Дж.; Поллак, Р. (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя , Contemp. Матем., вып. 453, Провиденс, Род-Айленд: AMS, стр. 49–86 .
Бандельт, Х.-Ю.; Ван де Вель, М. (1989), «Вложение топологических медианных алгебр в произведения дендронов» , Труды Лондонского математического общества , s3-58 (3): 439–453, doi : 10.1112/plms/s3-58.3.439 , заархивировано из оригинала 15 апреля 2013 г.
Бартелеми, Ж.-П.; Леклерк, Б.; Монжарде, Б. (1986), «Об использовании упорядоченных множеств в задачах сравнения и согласования классификаций», Journal of Classification , 3 (2): 187–224, doi : 10.1007/BF01894188 , S2CID 6092438 .
Имрих, Вильфрид; Клавжар, Санди; Малдер, Генри Мартин (1999), «Медианные графики и графики без треугольников», SIAM Journal on Discrete Mathematics , 12 (1): 111–118, CiteSeerX 10.1.1.28.5906 , doi : 10.1137/S0895480197323494 , MR 1666073 .
Пропп, Джеймс (1997), «Генерация случайных элементов конечных дистрибутивных решеток», Electronic Journal of Combinatorics , 4 (2): R15, arXiv : math.CO/9801066 , doi : 10.37236/1330 , S2CID 13313188 .

[1] Бартелеми, Леклерк и Монжарде (1986) , стр. 200.

[2] Пропп (1997) .

[3] Имрих, Клавжар и Малдер (1999) приписывают введение симплексных графов более поздней статье, также Бандельту и ван де Велю, но это кажется ошибкой.

[1]

[2]

[3]