Анотація до роботи:

Семенюта М. Ф. Дослідження розкладів та нумерацій графів. – Рукопис.

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

В дисертації отримано ряд нових результатів про розклади графів та нумерації. Побудовою доведено існування циклічного (К₂₁,G)-розкладу для кожного із 132 неізоморфних зв’язних (7,10)-графів G. В роботі представлені результати про циклічні пентагональні розклади графа К_п, серед яких спосіб побудови базових компонент таких розкладів, алгоритми і програми побудови списку та специфікаційних інваріантів для (К₁₁,С₅)- і (К₂₁,С₅)-розкладів. Для розрізнення-ототожнення циклічних (К₁₁,С₅)- і (К₂₁,С₅)-розкладів введено графічні інваріанти. Знайдено список неізоморфних циклічних (К₁₁,С₅)-розкладів, верхню оцінку числа неізоморфних циклічних пентагональних розкладів графа К_п, нижні оцінки числа неізоморфних циклічних(К₂₁,С₅)- та (K₁₉, G)-розкладів, коли G=П – трикутна призма, G=В – барвінок.

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

В дисертації описано метод побудови стандартної нумерації дерев і з її допомогою встановлено антимагічність подвійних зірок, r-регулярних дерев, k-ярусних (r₀, r₁, …, r_k)-регулярних монотонно спадних дерев. Знайдено одну з антимагічних нумерацій простих ланцюгів Р_n (n>2), простих циклів С_n (n3), повних графів К_n. Доведено антимагічність голландських m-вітряків, графів С_nР₃ і B(C_n, P₂, C_n), побудовано алгоритм перевірки графа на антимагічність.

В дисертаційній роботі отримано низку результатів про побудову, перелік циклічних (К_п, G)-розкладів для певних графів G і 1-факторизацій n-вимірного куба Q_n та про реберну антимагічність графів.

Дисертантом встановлено, що для кожного з 132 існуючих неізоморфних зв’язних (7,10)-графів G існує циклічний (К₂₁, G)-розклад, і знайдено базову компоненту одного з таких розкладів. Під час розгляду циклічних пентагональних розкладів введено поняття кортежу довжин, базового набору довжин. Розроблено спосіб побудови базових компонент циклічного (К_n, С₅)-розкладу. Він може бути модифікований на випадок циклічних (К_n, С_m)-розкладів. На основі цього способу знайдено алгоритми і складено програми пошуку списків циклічних (К₁₁, С₅)- та (К₂₁, С₅)-розкладів. Для розрізнення-ототожнення розкладів введено узагальнений граф верхніх ребер G_УВ та графи Inb(R) і Inс(R), що є графічними інваріантами. Застосування специфікаційного інваріанта – таблиці Т(R) та графічних інваріантів у множині циклічних (К_n, С₅)-розкладів дало можливість одержати вичерпний список неізоморфних пентагональних циклічних розкладів графа К₁₁ та нижню оцінку числа неізоморфних циклічних (К₂₁, С₅)-розкладів. Доведено необхідну умову ізоморфності циклічних (К_п, С₅)-розкладів. Знайдено верхню оцінку числа неізоморфних циклічних (К_п, С₅)-розкладів, а також нижню оцінку числа неізоморфних циклічних призматичних та барвінкових розкладів графа K₁₉.

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

В загальному вигляді описано метод побудови реберної нумерації дерев, яку названо стандартною. Введено поняття вершинного яруса центрального дерева, повного ярусного (r₀, r₁, … ,r_k)-регулярного дерева, монотонно спадного та монотонно зростаючого дерев. Із застосуванням стандартної нумерації доведено антимагічність подвійних зірок порядку n (n5), r-регулярних дерев та повних k-ярусних (r₀, r₁, … ,r_k)-регулярних монотонно спадних дерев при k 2. Знайдено одну з антимагічних нумерацій простого ланцюга, простого цикла, повного графа, голландського вітряка, графів С_nР₃ і B(C_n, P₂, C_n). Складено алгоритм перевірки графа на антимагічність. Отримані результати, що стосуються нумерацій графів, можна охарактеризувати, як загальний підхід до знаходження антимагічних нумерацій певних спеціальних графів та дослідження часткових випадків при застосуванні програми, яка реалізує побудований алгоритм.

Публікації автора:

1. Семенюта М. Ф. Антимагічна нумерація графів // Вісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. – 2005. – Вип. №3. – С. 90–98.

2. Семенюта М. Ф. 1-факторизації булевих кубів // Вісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. – 2006. – Вип. №2. – С. 50–56.

3. Семенюта М. Ф. Циклічні пентагональні розклади повного графу // Вісник Київського національного університету ім. Т. Шевченка. Серія: фізико-математичні науки. – 2006. – Вип. №3. – C. 53–59.

4. Семенюта М. Ф. Циклічні розклади графу К_n на графи малих порядків // Вісник Тернопільського державного технічного університету ім. І. Пулюя. – 2006. – Т.11, №4. – С. 160–170.

5. Semenyuta M. F. Antimagic graph labelings // Тези доповідей V-ої Міжнародної алгебраїчної конференції в Україні. – Одеса: Одеський нац. університет ім. І. І. Мечникова, 2005. – C. 184.

6. Семенюта М. Ф., Сорока О. О. 1-факторизації булевих кубів // Матеріали IX Міжнародної науково-практичної конференції "Наука та освіта – 2006" - Дніпропетровськ: Наука і освіта, 2006. – Т. 13. - С. 68–71.

7. Семенюта М. Ф. Циклічні розклади К₂₁ на (7,10)-графи // Одинадцята міжнародна наукова конференція імені академіка М. Кравчука, Київ: Матеріали конф. – К.: ТОВ «Задруга», 2006. – С. 588.

8. Semenyuta M. Cyclic pentagonal decompositions of К₁₁ // Тези доповідей Міжнародної конференції по радикалах ICOR-2006. – Київ.: Київський нац. університет ім. Т. Шевченка, 2006. – С. 60–61.

9. Семенюта М. Ф., Сорока О. О. Побудова циклічних пентагональних розкладів повних графів// Матеріали першого міжвузівського науково-практичного семінару “Комбінаторні конфігурації та їх застосування”. – м. Кіровоград: Видавництво ДЛАУ, 2006 р. – С. 43–44.

10. Semenyuta M. F. On cyclic decompositions of graphs // Тези доповідей VI-ої Міжнародної алгебраїчної конференції в Україні. – Кам’янець-Подільський: Кам’я нець-Подільський держ. університет, 2007. – С. 182–183.