Петренюк Д. А. Методи розв'язання задачі розкладу повних графів на підграфи

Дисертаційна робота присвячена розкладам повного графу K13 на кубічні компоненти заданого виду, а також методам отримання та умовам існування півобертових T факторизацій повного графу та їхньому зв'язку з нумерацією вершин дерева. Для графа K13 досліджено існування кубічних розкладів, у яких будь-які дві компоненти одного й того ж порядку ізоморфні, розкладів, у яких компоненти однакових порядків не обов'язково ізоморфні, а також розкладів, у яких одна з компонент десятого порядку ізоморфна графу Петерсена. Доведено, що всі півсиметричні дерева порядків 18, 20 та 22 допускають півобертову T факторизацію відповідного повного графа. Для доведення використано поняття граціозної нумерації дерева. Задача існування півобертової Т-факторизації для даного півсиметричного дерева зводиться до відшукання граціозної нумерації симетричної половини цього дерева. Запропоновано нові методи отримання граціозної нумерації для окремих класів дерев - l зірки, (2, k) гусениці, p сніжинки. Доведено граціозність та запропоновано метод отримання граціозної нумерації для нових класів дерев - рівномірних омарів та r гусениць.