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

Еквівалентне визначення таке: граф є пороговим, якщо існує дійсне число ${\displaystyle S}$ і для кожної вершини ${\displaystyle v}$ задано вагу ${\displaystyle w(v)}$, таку, що для будь-яких двох вершин ${\displaystyle v,u}$, ${\displaystyle uv}$ є ребром тоді й лише тоді, коли ${\displaystyle w(u)+w(v)>S}$ .

Інше еквівалентне визначення: граф є пороговим, якщо існує дійсне число ${\displaystyle T}$ і для кожної вершини ${\displaystyle v}$ задано вагу ${\displaystyle a(v)}$, таку, що для будь-якої множини вершин ${\displaystyle X\subseteq V}$, ${\displaystyle X}$ є незалежним тоді й лише тоді, коли ${\displaystyle \sum _{v\in X}a(v)\leq T.}$

Назва «пороговий граф» прийшла з визначення: S є «порогом» для властивості мати ребро, або, еквівалентно, T є порогом для множини «бути незалежним».

З визначення, що використовує послідовне додавання вершин, можна отримати альтернативний спосіб унікального опису порогового графу в сенсі рядка символів. ${\displaystyle \epsilon }$ завжди є першим символом рядка і означає першу вершину графу. Кожен наступний символ буде або ${\displaystyle u}$, який означає ізольовану вершину, або ${\displaystyle j}$, який означає додавання домінівної вершини. Наприклад, рядок ${\displaystyle \epsilon uuj}$ подає зірку з трьома листками, а ${\displaystyle \epsilon uj}$ — шлях із трьох вершин. Граф на малюнку можна подати рядком ${\displaystyle \epsilon uuujuuj}$.

Порогові графи є окремим випадком кографів, розщеплюваних графів і тривіально досконалих графів[4]. Будь-який граф, який є одночасно кографом і розщеплюваним графом, є пороговим. Будь-який граф, який є одночасно тривіально досконалим графом і доповненням тривіально досконалого графу, є пороговим графом. Порогові графи є також окремим випадком інтервальних графів. Всі ці зв'язки можна пояснити в термінах їх характеризації забороненими породженими підграфами. Кограф — це граф з відсутністю породжених шляхів із чотирма вершинами, P_4, а порогові графи — це графи без породжених підграфів P_4, C₄ або 2K₂[5]. C₄ — це цикл із чотирьох вершин, а 2K₂ — його доповнення, тобто два окремих ребра. Це також пояснює, чому порогові графи замкнуті за взяттям доповнення. P₄ є самодоповнюваним, а тому, якщо граф не містить породжених підграфів P_4, C₄ і 2K_2, його доповнення теж не буде їх мати[6].

Геґґернес і ін. показали, що порогові графи можна розпізнати за лінійний час. Якщо граф не є граничним, буде вказано перешкоду у вигляді P_4, C₄ або 2K₂.

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

• В.А.Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. — М. : «Наука», 1990. — ISBN 5-02-013992-0. § 50. Пороговые графы
• Václav Chvátal, Peter Ladislaw Hammer. Studies in Integer Programming (Proc. Worksh. Bonn 1975) / P. L. Hammer, E. L. Johnson, B. H. Korte, G. L. Nemhauser. — Амстердам : North-Holland, 1977. — Т. 1. — С. 145–162. — (Annals of Discrete Mathematics).
• Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Нью-Йорк : Academic Press, 1980.. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• N. V. R. Mahadev, Uri N. Peled. Threshold Graphs and Related Topics. — Elsevier, 1995..

• Порогові графи, інформаційна система про класи графів та їх включення.