Реберний граф

Нехай заданий граф G, тоді його реберний граф L(G)  — це такий граф, що

• будь-яка вершина графу L(G) являє ребро графу G.
• дві вершини графу L(G) суміжні тоді й лише тоді, коли їх відповідні ребра мають загальну вершину («суміжні») в G.

Властивості графу G, залежні лише від суміжності ребер, можуть бути переведені в еквівалентні властивості графу L(G), залежні лише від суміжності вершин. Наприклад, парування в G — це множина дуг, жодна з яких не суміжна з іншою, та відповідна множина вершин в L(G), жодна з яких не суміжна з іншою, тобто, незалежна множина вершин.

Отже,

• реберний граф зв'язного графу зв'язний. Якщо G зв'язний, він містить шлях, що з'єднує будь-які два його ребра, який перекладається в дорогу графу L (G), що містить будь-які дві вершини графу L(G). Тим не менш, графу G, який містить ізольовані вершини, а тому незв'язні, може відповідати зв'язний реберний граф.
• завдання про максимальну незалежну множину для реберного графу відповідає завданню знаходження максимального парування у вихідному графі.

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

• реберне хроматичне число графу G дорівнює вершинному хроматичному числу його реберного графу L(G).
• реберний граф реберно-транзитивного графу є вершинно-транзитивним графом.
• якщо граф G має Ейлерів цикл, тобто G зв'язаний і має парне число ребер у кожній вершині, то його реберний граф є гамільтоновим графом. (Проте не всі Гамільтонові цикли в реберному графі виходять з Ейлерових циклів.)
• реберний граф не має клешень, тобто породжених підграфів у вигляді трьох листків.
• реберний граф дерева є блоковим графом без клешень.

Дев'ять мінімальних нереберних графів із характеристик Байнеке (Beineke) заборонених підграфів реберних графів. Граф є реберним тоді і лише тоді, коли він не містить жоден з цих дев'яти графів, як породжений підграф.

Граф G є реберним графом якого-небудь іншого графу в тому й лише в тому випадку, коли можна знайти набір клік в G, які розбивають дуги графу G так, що кожна вершина G належить в точності двом клікам. Може статись, що для досягнення цього буде потрібно окремі вершини виділити в кліки. За теоремою Вітні[10][11], якщо G не є трикутником, може бути лише одне розбиття такого роду. Якщо розбиття існує, ми можемо побудувати граф, для якого G буде реберним графом шляхом створення вершини для кожної кліки та з'єднанням отриманих вершин ребром, якщо вершина належить обом клікам. Таким чином, за винятком ${\displaystyle K_{3}}$ та ${\displaystyle K_{1,3}}$, якщо два реберних графи зв'язаних графів ізоморфні, то і графи ізоморфні. Руссопоулос[12] використовував це спостереження, як базис для лінійного за часом алгоритму розпізнавання реберних графів та реконструкції їх вихідних графів.

Наприклад, така характеристика може бути використана, щоб показати, що такий граф не є реберним:

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

Інша характеристика графу була доведена Байнеке[13] (і була згадана без доведення раніше ним же[3]). Він показав, що є дев'ять мінімальних графів, які не є реберними, таких, що будь-який граф, що не є реберним, містить один з цих дев'яти графів як породжений підграф. Таким чином, граф є реберним тоді і лише тоді, коли ніяка підмножина вершин не породжує один з цих дев'яти. У прикладі, наведеному вище, чотири верхніх вершини породжують клішню (тобто, повний дводольний граф K _1,3), показаний вгорі ліворуч ілюстрації заборонених підграфів. Таким чином, за характеристикою Байнеке, цей граф не може бути реберним. Для графів зі ступенем вершин не менше 5 лише шість підграфів в лівому та правому стовпчиках малюнка можуть породжуватися графом[14]. Цей результат схожий на результат для реберних графів гіперграфу.[15]

Руідж та Вільф[16] розглянули послідовність графів

${\displaystyle G,\ L(G),\ L(L(G)),\ L(L(L(G))),\ \dots }$

Вони показали, що для кінцевого графу зв'язного графу ${\displaystyle G}$ можливі лише чотири види поведінки цієї послідовності:

• Якщо ${\displaystyle G}$ — циклічний граф, то ${\displaystyle L(G)}$ і всі такі ізоморфні самому графу ${\displaystyle G}$. Це єдине сімейство зв'язних графів, для яких ${\displaystyle L(G)}$ ізоморфно ${\displaystyle G}$.
• Якщо ${\displaystyle G}$ — клішня ${\displaystyle K_{1,3}}$, то ${\displaystyle L(G)}$ і всі такі графи є трикутниками.
• Якщо ${\displaystyle G}$ — шлях, то кожний такий реберний граф — скорочений шлях, поки він не перетвориться в порожній граф.
• У всіх інших випадках розмір графів збільшується необмежено.

Якщо ${\displaystyle G}$ незв'язний, то ця класифікація застосована до кожної окремої компоненти зв'язності графу ${\displaystyle G}$.

Будь-який реберний граф не містить клешень. Реберний граф дводольного графу є досконалим (дивись теорему Кеніга). Реберні графи дводольних графів створюють один з ключових блоків, який використовується для доведення теореми про досконалі графи. Спеціальним випадком є ​​турові графи, реберні графи повних дводольних графів.

• Реберно-досконалий граф

• Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X..