Факторизація графа

ФакторграфаG- це остовний підграф, тобто підграф, що має ті ж вершини, що і графG.k-факторграфа - це остовнийk-регулярний підграф, аk-факторизаціярозбиває ребра графа на непересічніk-фактори. Кажуть, що графGk-факторизуємо, якщо він дозволяєk-розбиття. Зокрема, безліч ребер1-фактора- це досконале паросполучення, а 1-розкладанняk-регулярного графа - це реберне забарвленняkквітами.2-фактор- це набір циклів, які покривають усі вершини графа.

Зміст

Якщо граф 1-факторизуємо (тобто має 1-факторизацію), він повинен бути регулярним графом. Проте чи всі регулярні графи є 1-факторизуемыми.k-регулярний граф є 1-факторизуемим, якщо його хроматичний індекс дорівнюєk. Приклади таких графів:

• Будь-який регулярний дводольний граф [1] [2] . За допомогою теореми Холла про весілля можна показати, щоk-правильний дводольний граф містить досконале поєднання. Можна тоді видалити досконале паросполучення та (k− 1)-регулярний дводольний граф і продовжити той самий процес рекурсивно.
• Будь-який повний граф з парною кількістю вершин (див. нижче) [3] . Однак єk-регулярні графи, хроматичний індекс яких дорівнюєk+ 1, і ці графи не 1-факторизуються. Приклади таких графів:
• Будь-який регулярний граф з непарним числом вершин.
• Граф Петерсен.

Повні графи

1-факторизація повного графа відповідає розбиттю на пари у кругових турнірах. 1-факторизація повних графів є спеціальним випадком теореми Бараньяї щодо 1-факторизації повних гіперграфів.

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

Число різних 1-факторизаційK2,K4,K6,K8, … дорівнює 1, 1, 6, 6240 , 1225566720, 252282619805368320, 98758655816833727741338583040, … (послідовність A000438 в OEIS).

Гіпотеза про 1-факторизацію

НехайG-k-регулярний граф з 2nвершинами. Якщоkдосить велике, відомо, щоGмає бути 1-факторизуємо:

• Якщоk= 2n− 1, тоGє повним графомK2n, а тому 1 -факторизуємо (див. вище).
• Якщоk= 2n− 2, тоGможна отримати шляхом видалення досконалого паросполучення зK2n. ЗновуGє 1-факторизується.
• Четвінд і Хілтон [4] показали, що приk≥ 12n/7 графG1-факторизуємо.

Гіпотеза про 1-факторизацію[5] є давно висунутою гіпотезою, яка стверджує, що значенняk≈nдосить велике. Точне формулювання:

• Якщоnнепарно іk≥n, тоG1-факторизуємо. Якщоnпарно іk≥n− 1, тоG1-факторизуємо.

Гіпотеза сильного заповнення [en] містить у собі гіпотезу про 1-факторизацію.

Досконала 1-факторизація

Досконала пара1-факторизацій - це пара 1-факторів, об'єднанняяких дає гамільтонів цикл.

Повна 1-факторизація(P1F) графа - це 1-факторизація, що має властивість, що будь-яка пара 1-факторів є досконалою парою. Досконала 1-факторизація не слід плутати з досконалим паросочетанням (яке також називають 1-фактором).

В 1964 Антон Котциг висловив припущення, що будь-який повний графK2n, деn≥ 2, має досконалу 1-факторизацію. Відомо, що наступні графи мають досконалі 1-факторизації [6] :

• Нескінченне сімейство повних графівK2p, деp- непарне просте (Андерсон і Накамура, незалежно),
• Нескінченне сімейство повних графівKp+ 1, деp- непарне просте
• спорадично інші графи, включаючи K 2n, де 2n∈ . Є й свіжіші результати тут.

Якщо повний графKn+ 1 має досконалу 1-факторизацію, то повний дводольний графKn,nтакож має досконалу 1-факторизацію [7] .

Якщо граф 2-факторизуємо, він повинен бути 2k-регулярним для деякого цілогоk. Юліус Петерсен показав у 1891, що ця необхідна умова є також достатньою — будь-який 2k-регулярний граф є 2-факторизованим [8] .

Якщо зв'язковий граф є 2k-регулярним і має парне число ребер, він також може бутиk-факторизуємо шляхом вибору двох факторів, що є ребрами, що чергуються ейлерового циклу [9] . Це стосується лише зв'язкових граф, незв'язні контрприклади містять незв'язне об'єднання непарних циклів або копій графаK2k+1.

---