Мінімальні вкладення повних графів та 1-занурення графів у двовимірні поверхні

Термін нещільності триангуляції поверхні був введеним в статтях Негамі (1999) та Танумі (1999), і була висловлена гіпотеза (Негамі, 2000), що є верхня межа для нещільності трикутного вкладення така, що ця межа не залежить від .

Основним результатом підрозділу 6.3 є

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

Доведення цієї теореми є цікавим прикладом того, як відомі нетривіальні результати стосовно систем трійок Штейнера можуть бути застосованими для побудови трикутних вкладень повного графа з деякими бажаними властивостями. Щоб довести Теорему 6.3.1, ми застосовуємо результати стосовно розфарбування систем трійок Штейнера. Строгим -розфарбуванням, , системи трійок Штейнера називається розфарбування елементів цієї системи фарбами у такий спосіб, що: кожна трійка має щонайменше два елементи того самого кольору; всі фарби використані; всі елементи пофарбовані. Поняття строгого розфарбування було спочатку означено для гіперграфів, а Мілаззо і Туза (1997) вперше застосували це поняття для вивчення систем трійок Штейнера і показали, що для кожного цілого числа , існує -розфарбована система трійок Штейнера порядку . Використовуючи ці результати, доведена

Лема 6.3.1 Для кожного цілого числа і для кожного припустимого , існує -розфарбована система трійок Штейнера порядку .

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

В підрозділі 6.4 досліджуються методи побудови взаємних вкладень систем трійок Штейнера.

Грань трикутного вкладення графа задає трійку вершин, інцидентних цієї грані. Дві системи та трійок Штейнера порядку називаються орієнтовно (відп. неорієнтовно) взаємно вкладеними, якщо існує таке гране 2-розфарбоване трикутне вкладення графа у орієнтовну (відп. неорієнтовну) поверхню, в якому множини граней одного кольору задають системи трійок Штейнера, ізоморфні системам та , відповідно. Сучасні компютерні обчислення показують, що є солідні аргументи на користь наступних двох глибоких гіпотез:

(a) Кожна пара систем трійок Штейнера порядку , чи mod 6 і , може бути взаємно вкладеною у неорієнтовну поверхню.

(b) Кожна система трійок Штейнера порядку , чи mod 12 і , має орієнтовне взаємне вкладення з деякою іншою системою трійок Штейнера порядку .

Циклічною системою трійок Штейнера порядку називається така система трійок Штейнера порядку з множиною точок , що якщо - трійка цієї системи, то для кожного , є також трійкою. Циклічна система трійок Штейнера порядку існує для або mod 6, за винятком .

В 1970 р. Янгс побудував одне орієнтовне взаємне вкладення двох циклічних систем трійок Штейнера порядку для кожного , і це взаємне вкладення було єдиним відомим в літературі орієнтовним взаємним вкладенням двох циклічних систем трійок Штейнера порядку для необмежено великих значень .

Теореми 6.4.1 та 6.4.2 дають характеризацію таких приписувань струмів дугам дводольного драбинно-подібного графа Мебіуса, що приводять до каскадів з групою струмів , які породжують орієнтовні взаємні вкладення циклічних систем трійок Штейнера порядку . Використовуючи цю характеризацію, Теорема 6.4.5 для кожного дає щонайменше неізоморфних орієнтовних взаємних вкладень циклічних систем трійок Штейнера порядку .

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

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

В підрозділі 7.1 вивчаються графи, що можуть бути 1-зануреними у площину (1-планарні) графи).

Мало що відомо стосовно 1-планарних графів. Бородін (1984) довів. що 6 є максимальним хроматичним числом 1-планарних графів. Деякі властивості 1-планарних графів вивчалися Шумахером (1980), Фабріці та Мадараш (2007), Ченом (2001, 2004). Ще менше відомо про не-1-планарні графи. Єдиними відомими результатами є статті дисертанта [7,19].

Граф називається мінімальним не-1-планарним графом, якщо граф не є 1-планарним, але граф є 1-планарним для кожного ребра графа .

Проблема побудови мінімальних не-1-планарних графів тісно пов'язана з проблемою визначення, чи є даний граф 1-планарним. За теоремою Куратовського, планарність графа може бути охарактеризована в термінах заборонених мінорів і . Але 1-планарність графа не може бути охарактеризована в термінах заборонених мінорів. оскільки, як легко показати, існує 1-планарне підрозбиття кожного графа, тобто множина 1-планарних графів не є замкненою відносно утворення мінорів. Кожний не-1-планарний граф містить як підграф деякий мінімальний не-1-планарний граф, який можна отримати відкиданням деяких ребер графа так, щоб отриманий граф залишався не-1-планарним. Якщо мінімальних не-1-планарних графів була б скінченна кількість, то тоді була існувала б наступна характеризація 1-планарних графів: граф є 1-планарним тоді і тільки тоді, коли він не містить як підграф мінімальні не-1-планарні графи.

Основним результатом підрозділу 7.1 є

Теорема 7.1.1 Існує нескінченно багато мінімальних не-1-планарних графів.

Щоб довести цю теорему, застосовується Лема 7.1.1, яка дає можливість довести існування мінімального не-1-планарного графа, число ребер якого лежить у деякому відомому інтервалі.

Лемма 7.1.1 Якщо існує не-1-планарний граф такий, що граф є 1-планарним для деяких ребер графа , то тоді граф містить як підграф мінімальний не-1-планарний граф такий, що .

У доведенні Теореми 7.1.1, для кожного будується не-1-планарний граф , , такий, що граф є 1-планарним для деяких ребер графа . Не-1-планарний граф , , містить підграф , що має тільки одне можливе 1-занурення у площину. Це 1-занурення графа заважає розмістити всі інші ребра графа на площині так, щоб отримати 1-занурення графа у площину.

В підрозділах 7.2 і 7.3 вивчається 1-хроматичне число поверхні.

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

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

Позначимо через орієнтовну поверхню роду і через неорієнтовну поверхню роду . Ейлерова характеристика поверхні дорівнює , якщо , і дорівнює , якщо .

Рінгель (1981) отримав наступну верхню межу для : якщо , то

,

причому, якщо і - парне, то

,

де ми означили функцію . Рінгель висунув гіпотезу, що ця межа є точною для всіх поверхонь (за виключенням, може бути, декількох поверхонь малого роду). Було доведено, що для наступних поверхонь: , , (Рінгель (1981)); (Бородин (1984); виявилося, що для сфери дуже важко знайти 1-хроматичне число); і для дев'яти інших поверхонь малого роду (Коржик [2]). Шумахер (1984) показав, що . Коржик [4] довів, що для кожної поверхні .

Основним результатом підрозділу 7.2 є

Теорема 7.2.1 для кожної поверхні .

В підрозділах 7.2 та 7.3 розроблено методи побудови 1-занурень повних графів необмежено великого порядку.

Оскільки граф має хроматичне число , то щоб довести нерівність для поверхні , достатньо побудувати 1-занурення графа у поверхню . Леми 7.2.1 і 7.2.2 зводять задачу доведення Теореми 7.2.1 до задачи побудови такої сім'ї орієнтовних 1-занурень повних графів необмежено великого порядку, що із існування цієї сім'ї випливає існування 1-занурення графа кожну поверхню . У ході доведення Теореми 7.2.1, для кожного такого 1-занурення графа у поверхню , що належить до сім'ї , ми будуємо каскад, що породжує орієнтовне вкладення підграфа графа у поверхню таке, що, додаючи пари схрещених ребер у чотирикутні грані цього вкладення, дістаємо бажане 1-занурення графа у поверхню .

Для цілого числа , -орієнтовною (відп. неорієнтовною) послідовністю називається така нескінченна послідовність орієнтовних (відп. неорієнтовних) поверхонь, що для всіх . У ході доведення Теореми 7.2.1 побудовано -орієнтовні і неорієнтовні послідовності для (включаючи ). Проблема побудови -орієнтовних послідовностей для залишається відкритою. В підрозділі 7.3 будується -неорієнтовна послідовність.

В підрозділі 7.3 розглядається задача побудови нескінченних сімей неорієнтовних поверхонь з відомим 1-хроматичним числом. Раніше було доведено (Коржик [5]), що якщо - первісний корінь по модулю простого числа , де - ціле число і не є mod 3, то тоді . Невідомо, чи існує нескінченно багато таких , але є аргументи (як і у випадку Теореми 5.2.1) на користь того, що таких значень нескінченно багато.

Основним результатом підрозділу 7.3 є

Теорема 7.3.1 Для цілого , якщо - просте число, то .

Оскільки 3 і 4 - взаємно прості числа, то, за відомою теоремою Діріхле, арифметична прогресія , , містить нескінченно багато простих чисел. Таким чином, побудовано нескінченну сім'ю неорієнтовних поверхонь з відомим 1-хроматичним числом (і це число дорівнює верхній межі Рінгеля).

Висновки

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

Топологічна теорія графів, як самостійний напрямок дослідження, бере свій початок з доведення Рінгелем і Янгсом у 1968 році теореми про розфарбування карт на двовимірних орієнтовних та неорієнтовних поверхнях, відмінних від сфери.

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

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

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

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

Знайдено найменшу ненульову відстань між двома трикутними вкладеннями повного графа і отримано нетривіальну нижню межу для максимальної відстані між двома трикутними вкладеннями деяких повних графів.

Запропоновано новий підхід у застосуванні систем трійок Штейнера для побудови трикутних вкладень повних графів.

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

Цим дано негативну відповідь на відкриту проблему Негамі (2000). Розроблено методи побудови дводольних каскадів, що породжують орієнтовні взаємні вкладення циклічних систем трійок Штейнера. Як наслідок, побудовано багато неізоморфних орієнтовних взаємних вкладень циклічних систем трійок Штейнера порядку .

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

Розроблено методи побудови 1-занурень повних графів необмежено великого порядку.

За допомогою графів струмів індексу один, знайдено з точністю до 10 1-хроматичне число кожної поверхні, орієнтовної чи неорієнтовної. Побудовано нескінченну сім'ю неорієнтовних поверхонь з відомим 1-хроматичним числом, яке дорівнює верхній межі Рінгеля.

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

Список опублікованих робіт за темою дисертації

1. Korzhik V. Realizing the chromatic numbers of triangulations of

surfaces / V. Korzhik, F. Harary, S. Lawrencenko // Discrete Mathematics. - 1993. - Vol. 122. - P. 197-204.

2. Korzhik V. A lower bound for the one-chromatic number of a surface / V. Korzhik // Journal of Combinatorial Theory Ser. B. - 1994. - Vol. 61. - P. 40-56.

3. Korzhik V. A nonorientable triangular embedding of , mod 12 / V. Korzhik // Discrete Mathematics. - 1995. - Vol. 141. - P. 195-211.

4. Korzhik V. A tighter bounding interval for the 1-chromatic number of a surface / V. Korzhik // Discrete Mathematics. - 1997. - Vol. 169. - P. 95-120.

5. Korzhik V. A possibly infinite series of surfaces with known 1-chromatic number / V. Korzhik // Discrete Mathematics. - 1997. - Vol. 173. - P. 137-149.

6. Korzhik V. An infinite series of surfaces with known 1-chromatic number / V. Korzhik // Journal of Combinatorial Theory Ser. B. - 1998. - Vol. 72. - P. 80-90.

7. Korzhik V. Nonadditivity of the 1-genus of a graph / V. Korzhik // Discrete Mathe\-matics. - 1998. - Vol. 184. - P. 253-258.

8. Korzhik V. Triangular embeddings of with unboundedly large $m$ / V. Korzhik // Discrete Mathematics. - 1998. - Vol. 190. - P. 149-162.

9. Korzhik V. On the number of nonisomorphic orientable regular embeddings of complete graphs / V. Korzhik, H.-J. Voss // Journal of Combinatorial Theory Ser. B. - 2001. - Vol. 81. - P. 58-76.

10. Korzhik V. Another proof of the Map Color Theorem for nonorientable surfaces / V. Korzhik // Journal of Combinatorial Theory Ser. B. - 2002. - Vol. 86. - P. 221-253.

11. Korzhik V. Exponential families of nonisomorphic nontriangular orientable genus embeddings of complete graphs / V. Korzhik, H.-J. Voss // Journal of Combinatorial Theory Ser. B. - 2002. - Vol. 86. - P. 186-211.

12. Korzhik V. On the minimal nonzero distance between triangular embeddings of a complete graph / V. Korzhik, M. Grannell, T. Griggs, J. Siran // Discrete Mathematics. - 2003. - Vol. 269. - P. 149-160.

13. Korzhik V. Exponential families of nonisomorphic nonorientable genus embeddings of complete graphs / V. Korzhik, H.-J. Voss // Journal of Combinatorial Theory Ser. B. - 2004. - Vol. 91. - P. 253-287.

14. Korzhik V. Nonorientable biembeddings of Steiner triple systems / V. Korzhik, M. Grannell // Discrete Mathematics. - 2004. - Vol. 285. - P. 121-126.

15. Korzhik V. On the voltage-current transferring in topological graph theory / V. Korzhik, V. Alekseyev // Ars Combinatoria. - 2005. - Vol. 74. - P. 331-349.

16. Korzhik V. Small surface trades in triangular embeddings / V. Korzhik, G. Bennett, M. Grannell, T. Griggs, J. Siran // Discrete Mathematics. - 2006. - Vol. 306. - P. 2637-2646.

17. Korzhik V. On the maximal distance between triangular embeddings of a complete graph / V. Korzhik // Journal of Combinatorial Theory Ser. B. - 2006. - Vol. 96. - P. 426-435.

18. Korzhik V. A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs / V. Korzhik, Kwak Jin Ho // Discrete Mathematics. - 2008. - Vol. 308. - P. 1072-1079.

19. Korzhik V. Minimal non-1-planar graphs / V. Korzhik // Discrete Mathematics. - 2008. - Vol. 308. - P. 1319-1327.

20. Korzhik V. Exponentially many nonisomorphic orientable triangular embeddings of / V. Korzhik // Discrete Mathematics. - 2008. - Vol. 308. - P. 1046-1071.

21. Korzhik V. Nonorientable triangular embeddings of complete graphs with arbitrarily large looseness / V. Korzhik, Kwak Jin Ho // Discrete Mathematics. - 2008. - Vol. 308. - P. 3208-3212.

22. Korzhik V. Exponentially many nonisomorphic orientable triangular embeddings of / V. Korzhik // Discrete Mathematics. - 2009. - Vol. 309. - P. 852-866.

23. Korzhik V. Minimal obstructions for 1-immersions and hardness of 1-planarity testing / V. Korzhik, B. Mohar // Lecture Notes in Computer Science. - 2009. - Vol. 5417. - P. 302-312.

24. Korzhik V. Orientable biembeddings of cyclic Steiner triple systems from current assignments of the Mobius ladder graph / V. Korzhik, M. Grannell // Discrete Mathematics. - 2009. - Vol. 309. - P. 2847-2860.

25. Korzhik V. Complete triangulations of a given order generated from a multitude of nonisomorphic cubic graphs by current assignments / V. Korzhik // Journal of Graph Theory. - 2009. - Vol. 61. - P. 324-334.

26. Korzhik V. On the 1-chromatic number of nonorientable surfaces with large genus / V. Korzhik // Graph Embeddings and Maps on Surfaces 2005: an international workshop, June 26 - July 1, 2005: absracts - Stara Lesna, Slovakia, 2005. - P. 11.

27. Коржик В. П. Расстояние между треугольными вложениями полного графа в поверхность / В. П. Коржик // Дискретная математика и её приложения: 9 международный семинар, 18-23 июня 2005 г.: тезисы докл. - М. Из-во Моск. ун-та., 2007. - С. 280-283.

28. Korzhik V. Minimal obstructions for 1-immersions and hard\-ness of 1-planarity testing / V. Korzhik, B. Mohar // 16-th International Symposium on Graph Drawing: September 21-24, 2008: abstracts - Heraclion, Greece, 2008. - P. 12.

Анотація

Коржик В.П. Мінімальні вкладення повних графів та 1-занурення графів у двовимірні поверхні. - Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.01.08 - математична логіка, теорія алгоритмів та дискретна математика. - Київський національний університет імені Тараса Шевченка, Київ, 2010.

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

За допомогою систем трійок Штейнера побудовано нові сім'ї неізоморфних трикутних вкладень повних графів а також показано, що існують неорієнтовні трикутні вкладення повних графів з необмежено великою нещільністью.

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

Знайдено з точністю до 10 1-хроматичне число кожної поверхні, орієнтовної чи неорієнтовної. Побудовано нескінченну сім'ю неорієнтовних поверхонь з відомим 1-хроматичним числом.

Ключові слова: вкладення графа у поверхню, хроматичне число поверхні, повний граф, мінімальне вкладення, неізоморфні вкладення, трикутні вкладення, відстань між вкладеннями, граф струмів, один-занурення графа, один-хроматичне число поверхні.

Аннотация

Коржик В.П. Минимальные вложения полных графов и 1-вложения графов в двумерные поверхности. - Рукопись.

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.01.08 - математическая логика, теория алгоритмов и дискретная математика. - Киевский национальный университет имени Тараса Шевченко, Киев, 2010.

В диссертации исследуются минимальные вложения полных графов и 1-погружения графов в двумерные поверхности, причём особое внимание уделяется вопросам построения неизоморфных минимальных вложений полных графов и вопросам построения 1-погружений полных графов с целью нахождения 1-хроматического числа поверхности. В диссертации даётся более простое и короткое доказательство теоремы о раскраске карт для неориентируемых поверхностей. Это доказательство базируется на построении такой последовательности 12 конструкций графов токов индекса один, порождающих минимальные вложения полных графов, что каждая последующая конструкция этой последовательности получается в результате незначительного преобразования предыдущей конструкции этой последовательности.

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

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

Предложен новый подход в применении систем троек Штейнера для построения треугольных вложений полных графов. В этом подходе система троек Штейнера определяет способ, в соответствии с которым некоторые вспомогательные вложения объединяются, чтобы образовать треугольное вложение полного графа. Применяя этот метод, построено не менее неизоморфных неориентируемых треугольных вложений графа для бесконечного числа значений , mod 3 (это первый такой результат для этого класса графов). Также показано, что существуют неориентируемые треугольные вложения полных графов с неограниченно большой неплотностью. Этим дано отрицательный ответ на открытую гипотезу Негами (2000). Разработаны методы построения двудольных каскадов, которые порождают ориентируемые взаимные вложения циклических систем троек Штейнера.

Граф 1-погружен в поверхность, если он представлен на этой поверхности так, что каждое его ребро пересекается не более чем с одним другим ребром. Показано, что существует бесконечно много минимальных графов, которые не могут быть 1-погруженными в плоскость. Разработаны методы построения 1-погружений полных графов неограниченно большого порядка. Определено с точностью до десяти 1-хроматическое число каждой поверхности, ориентируемой или неориентируемой. Построено бесконечное семейство неориентируемых поверхностей с известным 1-хроматическим числом.

Ключевые слова: вложение графа в поверхность, хроматическое число поверхности, полный граф, минимальное вложение, неизоморфные вложения, треугольные вложения, расстояние между вложениями, граф токов, один-вложение графа, один-хроматическое число поверхности.

Abstract

Korzhik V.P. Minimal embeddings of complete graphs and 1-immersions of graphs in two-dimensional surfaces. - Manuscript.

Thesis for the degree of Doctor of Physics and Mathematics in speciality 01.01.08 - mathematical logic, theory of algorithms and discrete mathematics. - Kyiv National Taras Shevchenko University, Kyiv, 2010.

In the thesis minimal embeddings of complete graphs and 1-immersions of graphs in two-dimensional surfaces are considered, where a special attention is paid to constructing nonisomorphic minimal embeddings of complete graphs and constructing 1-immersions of complete graphs with the aim of finding the 1-chromatic number of a surface. We give more short and simple proof of the Map Color Theorem for nonorientable surfaces. We show that there are constants such that for every the complete graph has at least nonisomorphic orientable and nonorientable minimal embeddings. The minimal nonzero distance between two triangular embeddings of a complete graph is found. We obtain a nontrivial lower bound on the maximal distance between two triangular triangular embeddings of some complete graphs. Using Steiner triple systems, we construct new families of nonisomorphic triangular embeddings of complete graphs and prove that there exist nonorientable triangular embeddings of complete graphs with unboundedly large looseness. Methods of constructing nonisomorphic orientable biembeddings of cyclic Steiner triple systems are developed. We show that there are infinitely many minimal graphs that have no 1-immersions in the plane. The 1-chromatic number of every surface, orientable or nonorientable, is found up to 10. We find an infinite series of surfaces with known 1-chromatic number.

Key words: embedding of a graph in a surface, chromatic number of a graph, complete graph, minimal embedding, nonisomorphic embeddings, triangular embeddings.

Размещено на Allbest.ru