Шерман З. О. Екстремальні розмітки вершин та ребер графів

Дисертація присвячена проблемі розмітки графів різних класів та видів. Виконано аналіз та систематизацію методів побудови граціозної розмітки графів, що є історично першою розміткою та лежить в основі знаходження інших типів розміток. В результаті аналізу виділено основні універсальні та спеціальні методи побудови граціозної розмітки графів. До спеціальних методів віднесено: метод переносу гілок та ребер, метод Δ-побудови, функціональну залежність та рекурсивний метод. До універсальних методів віднесено: метод цілочисельного програмування. Крім цього знайдено умови існування Фібоначчі граційної, квадратної сумарної та квадратної різницевої розміток. Розроблені способи їх побудови для нових класів графів. Сформульовано та розв’язано ряд задач на існування Фібоначчі граціозної розмітки для деяких графів циклічної структури. А саме для наступних графів: ланцюгового з'єднання циклів, одноточкового з'єднання циклів, довільного ланцюгового з'єднання циклів, графа nCm. Розроблені методи побудови квадратної сумарної розмітки для наступних графів: одноточкового з'єднання будь-якого квадратного сумарного графа з ланцюгом, реберного з'єднання n копій цикла C3 та ланцюга, графа, отриманого в результаті ланцюгового з'єднання циклів, тотального графа ланцюга та диз'юнктивного об'єднання будь-якого числа квадратних сумарних графів. Отримані нові результати, повязані з методами побудови квадратної різницевої розмітки, для наступних графів: одноточечного з'єднання циклів Cm для будь-якого непарного m, одноточечного з'єднання n копій циклу Cm й n копій ланцюга P2, диз'юнктивного об'єднання одноточечного з'єднання n копій циклу Cm з ланцюгом Pn, графів-гусениць, ланцюгового з u1108 єднання циклів, диз'юнктивного об'єднання зірок та диз'юнктивного об'єднання будь-якого SD графа з ланцюгом. Доведена гіпотеза про існування квадратної різницевої розмітки для цикла-кактуса. У дисертаційній роботі отримані нові результати, пов'язані з методами побудови нових квадратно різницевих дерев з відомих квадратно різницевих дерев. Для побудови нового дерева обрано метод Δ-побудови та три основні його підходи: ототожнення вершин з найбільшою міткою ізоморфних копій одного квадратно різницевого дерева; використання нової вершини й ребер, що з’єднують ізоморфні копії одного квадратно різницевого дерева; метод Δ-побудови, з використанням двох квадратних різницевих дерев.