Пороговый граф

Пример порогового графа.

В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций:

1. Добавление в граф одной изолированной вершины
2. Добавление одной доминирующей вершины в граф, т.е. отдельной вершины, связанной со всеми остальными вершинами.

Например, граф на рисунке является пороговым графом. Он может быть построен с одной вершины (вершина 1), и добавления чёрных вершин как изолированных вершин и красных вершин как доминирующих вершин в порядке нумерации.

Пороговые графы были введены Хваталом и ХаммеромШаблон:Sfn. Глава, посвящённая графам, появилась в книге ГолумбикаШаблон:Sfn, а книга Махадева и ПеледаШаблон:Sfn полностью посвящена пороговым графам.

Альтернативные определения

Эквивалентное определение следующее: граф является пороговым, если существует вещественное число $S$ и для каждой вершины $v$ задан вес $w(v)$, такой, что для любых двух вершин $v,u$, $uv$ является ребром тогда и только тогда, когда $w(u)+w(v)>S$.

Другое эквивалентное определение: граф является пороговым, если существует вещественное число $T$ и для каждой вершины $v$ задан вес $a(v)$, такой, что для любого множества вершин $X\subseteq V$, $X$ является независимым тогда и только тогда, когда $\sum _{v\in X}a(v)\le T.$

Название "пороговый граф" пришёл из определения: S является "порогом" для свойства иметь ребро, или, эквивалентно, T является порогом для множества быть независимым.

Разложение

Из определения, использующего последовательное добавление вершин, можно получить альтернативный путь уникального описания порогового графа в смысле строки символов. $ϵ$ всегда служит первым символом строки и представляет первую вершину графа. Каждый последующий символ будет либо $u$, который означает изолированную вершину, либо $j$, который означает добавление доминирующей вершины. Например, строка $ϵuuj$ представляет звезду с тремя листьями, а $ϵuj$ представляет путь из трёх вершин. Граф на рисунке можно представить строкой $ϵuuujuuj$

Связные классы графов и распознавание

Пороговые графы являются специальным случаем Кографов, расщепляемых графов и тривиально совершенных графовШаблон:Sfn. Любой граф, являющийся одновременно кографом и расщепляемым графом, является пороговым. Любой граф, являющийся одновременно тривиально совершенным графом и дополнением тривиально совершенного графа, является пороговым графом. Пороговые графы являются также специальным случаем интервальных графов. Все эти связи могут быть объяснены в терминах их характеризации запрещёнными порождёнными подграфами. Кограф — это граф с отсутствием порождённых путей с четырьмя вершинами, P₄, а пороговые графы — это графы баз порождённых подграфов P₄, C₄ или 2K₂ Шаблон:Sfn. C₄ — это цикл из четырёх вершин , а 2K₂ — его дополнение, то есть два раздельных ребра. Это также объясняет, почему пороговые графы замкнуты по взятию дополнения. P₄ является самодополнительным, а потому, если граф не содержит порождённые подграфы P₄, C₄ и 2K₂, его дополнение тоже не будет их иметь Шаблон:Sfn.

Хеггернес и др. показали, что пороговые графы могут быть распознаны за линейное время. Если граф не является пороговым, препятствие в виде P₄, C₄ или 2K₂ будет указано.

См. также

• Индифферентный граф
• Параллельно-последовательный граф

Литература

• Шаблон:Книга §50. Пороговые графы
• Шаблон:Книга.
• Шаблон:Книга. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Шаблон:Книга.

Ссылки

• Threshold graphs Шаблон:Wayback, Information System on Graph Classes and their Inclusions.