Степінь графа

У теорії графів, графом k-степені G^k неорієнтованого графа G є інший граф, що має таку ж саму кількість вершин, але дві його вершини є суміжними, коли відстань між ними не перевищує k. Аналогічну термінологію використовують при піднесенні чисел до степеня: G² називається G квадрат, G³ називається G куб, тощо.

Квадрат графа

Степінь графа слід відрізняти від добутку графа на себе, який (на відміну від графа в степені) має набагато більше вершин, ніж початковий граф.

Властивості

Якщо граф має діаметр d, то його граф d-степені — повний граф.

Розфарбовування

Розфарбовування квадрату графа може бути використано для розподілення учасників бездротової  мережі зв'язку таким чином, щоб ніякі два учасники не заважали один одному чи спільним сусідам, та для того, щоб виявити візуалізацію графа з найбільшою кутовою роздільністю.

Хроматичне число та виродження планарного графа степені k максимального ступеня Δ дорівнює $O(\Delta ^{\lfloor k/2\rfloor })$, де оцінка виродження відображає, що для розфарбування графа такою великою кількістю кольорів може бути використаний алгоритм жадібної розмальовки. Для окремого випадку квадрата планарного графа у 1977 році Вегнер висловив припущення, що хроматичне число квадрату планарного графа не перевищує $\max \left(d+5,{\frac {3d}{2}}+1\right)$, так само відомо, що хроматичне число не перевищує ${\frac {5d}{3}}+O(1)$. Взагалі, для будь-якого графа з виродженням d та максимальним степенем Δ, виродження квадрату графа дорівнює O(dΔ), тож для багатьох з щільних графів, окрім планарних, так само хроматичне число квадрату пропорційне Δ.

Незважаючи на те, що хроматичне число квадрату непланарного графа може бути пропорційним (у найгіршому випадку) Δ, воно буде меншим для графів з великим обхватом, обмежених у цьому випадку O(Δ²/log Δ).

Визначення мінімальної кількості кольорів, необхідних для розфарбування квадрат графа є NP-складною задачею, навіть у випадку з планарним графом.

Гамільтоновість

Куб кожного зв'язного графа обов'язково містить Гамільтонів цикл. Але квадрат зв'язного графа не обов'язково є гамільтоновим, і це є NP-повною задачею — виявити, чи є квадрат гамільтоновим. Проте, за теоремою Фляйшнера, квадрат 2-вершинно-зв'язного графа завжди є гамільтоновим.

Складність обчислення

Граф степені k, що має n вершин і m ребер може бути обчислений за О(mn) часу, за допомогою виконання пошуку в ширину, починаючи з кожної вершини для визначення відстані до всіх інших вершин. Як альтернатива, якщо А — матриця суміжності для графа, у якому змінені усі нульові елементи на головній діагоналі (на ненулеві), то ненулеві елементи матриці А^к дають матрицю суміжності графа степеня k, з цього випливає, що побудова степені k може бути здійснена за той час, що знаходиться у межах логарифмічного фактору часу для множення матриць.

Поняття степені листа тісно пов'язано з k-степенем дерева, індуковане листям дерева G. Цей клас графів знайшов застосування у філогенезі.

Було досягнуто першого твердого результату: Маючи граф, вирішити, чи є квадрат іншого графа NP-повною задачею. Крім того, NP-повною задачею є визначити, чи є граф степенем іншого графа коли k ≥ 2 , чи є він k-степенем двочастинного графа при k>2.