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

Петренюк А.Я. Екстремальні розклади повних графів: існування, перелік. - Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук зі спеціальності 01.05.01 - теоретичні основи інформатики та кібернетики, Інститут кібернетики ім.В.М.Глушкова НАН України, Київ, 2002.

Захищаються результати, опубліковані у 51 праці і присвячені задачам існування та переліку, з точністю до ізоморфізму, розкладів повних графів на компоненти, взяті з певних класів графів. Запропоновано кілька методів побудови таких розкладів – метод Н-перетворень, метод гніздування, біциклічний та напівобертовий. Одержано нові умови існування
Т-факторизацій повних графів, повністю розв'язана задача про існування
T-факторизацій порядку 10 та задача про існування біциклічних T-факторизацій порядку 14. Отримані результати переліку T-факторизацій, 1-факторизацій та розкладів повних графів на колеса, на зірки, на митри, на 5-цикли, на
D-фактори, на кубічні графи. Зокрема, проведено повний перелік кубічних факторизацій графа K₁₀.

У дисертації викладено результати, одержані дисертантом у розв'язуванні задач побудови та переліку розкладів графів, здебільшого повних, на підграфи, взяті з певних класів графів. Теоретичні досягнення та практичні результати, які отримав дисертант:

1. Знайдено способи представлення графів (зокрема, шаблонне представлення), зручні для побудови та переліку розкладів графів на підграфи відповідних типів.

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

3. Запропоновано кілька методів побудови розкладів повних графів, зокрема, метод H-перетворень кіркманових розкладів та метод гніздування, біциклічний та напівобертовий методи побудови деревних факторизацій.

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

5. Повністю вирішене питання про існування T-факторизацій порядку 10; задача існування T-факторизацій порядку 14 розв'язана для всіх дерев, за винятком 20.

6. Введено поняття розщеплення вектора степенів вершин дерева і на його основі одержано необхідні умови існування біциклічних T-факторизацій.

7. Запропоновано алгоритми переліку T-факторизацій, напівобертових та біциклічних T-факторизацій, за допомогою яких одержано ряд результатів переліку для порядків 10, 12 та 14.

8. Одержано необхідні умови існування та ряд результатів переліку різнокомпонентних деревних факторизацій.

9. Започатковано перелік W₄-розкладів графа K₁₇ отриманням вичерпних списків неізоморфних W₄-упаковок рангів r4 у граф K₁₇.

10. Одержано вичерпні списки розкладів повних графів на k-зірки для ряду значень параметрів.

11. Розв'язана задача Роса побудови спектра розмірів максимальних досконалих 1-факторизацій для порядку 12.

12. Побудовано вичерпний список досконалих 1-факторизацій порядку 12.

13. Повністю розв'язана проблема переліку мінімальних D-розкладів порядку 13.

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

15. Розпочато перелік пентагональних розкладів графа K₁₁: перелічено пентагональні упаковки рангів r3; перераховано гомогенні пентагональні упаковки для ряду значень параметрів; перераховано гомогенні пентагональні розклади графа K₁₁.

16. Проведено повний перелік розкладів графа K₁₀ на кубічні графи порядку 6 та повний перелік кубічних факторизацій графа K₁₀.

Основні положення дисертації опубліковані в таких працях:

1. Возняк В.В., Петренюк А.Я. Об одном алгоритме перечисления систем групп пар // Комбинаторный анализ. - 1972. - Вып.2. – С. 38–41.

2. Донец A.Г., Петренюк A.Я., О перечислении разнокомпонентных древесных разложений // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2000. – С. - 70–75.

3. Дурач Д., Приходькина А.И., Петренюк А.Я. О деревьях и древесных факторизациях // Научные труды академии. – 2001. - Вып.5. – Ч. 1. – Гос. летная академия Украины. – С. 34 -39.

4. Petrenjuk A.J., Zemljansky A. Enumerating cyclic 3-cube decompositions of K₂₅ // J. of Combin. Math. and Comb. Computing. – 2002. – 42. - Р. 88 - 96.

5. Курек Х.Є., Петренюк А.Я. О покрытии графов звездами // Теория графов. – Киев: Ин-т математики, УССР, 1977. – С. 145–156.

6. Петренюк А.Я. Минимальные D-разложения полных графов // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2001. - С. 43-49.

7. Петренюк А.Я. До перелiку розкладiв графа K₁₇ на колеса W₄. // Науковi записки. Сер. Фiзико-мат. науки. – Кiровоград, 1998. - Вип. XII. -

С. 56–61.

8. Петренюк А.Я. Древесные факторизации полных графов: существование, построение, перечисление // Материалы 7 Междунар. семинара "Дискретная математика и ее приложения". - М., 2001. – С. - 26–30.

9. Petrenjuk L.P., Petrenjuk A.J. Decomposition of the complete graph K(8) into smallest dragons // Світогляд. – 1995. – Вип. 1. - С. 101 – 108.

10. Петренюк А.Я., Необхідні умови існування Т-факторизацій // Доп. НАН України. - 2002. – № 3. – С. 71-73.

11. Петренюк А.Я. Каталог неизоморфных 5-гомогенных пентагональных 5-упаковок // Кибернетика и системный анализ. - 2001. – № 5. – С. 102–109

12. Петренюк А.Я. О построении неизоморфных блок-схем с помощью изографических наборов блоков / Кировоградский ин-т с.-х. машиностр. - Кировоград, 1983. – 11 с. - Рус. - Деп. в УкрНИИНТИ 30.08.89, N 985- Ук- 83.

13. Петренюк А.Я. О преобразованиях, приводящих к неизоморфным тактическим конфигурациям // Материалы Всесоюз. семинара по дискретной математике и ее приложениям. – М. Изд-во Моск. ун-та, 1986. – С. 81–87.

14. Петренюк А.Я. О спектре максимальных совершенных семейств 1-факторов в полных графах малых порядков // Оптимизация и ее приложения. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1997. – С. 60–68.

15. Петренюк А.Я. О существовании бициклических T-факторизаций порядка 14 // Научные труды академии. – 1999. - Вып.4. – Ч. 1. – Гос. летная академия Украины. – С. 206 -212.

16. Петренюк А.Я. О цилиндрических разложениях графов // Комбинаторный анализ. – 1986. - Вып.7. – С. 46–65.

17. Petrenjuk L.P., Petrenjuk A.J. Weighted blocking designs and their transformations // Світогляд. - 1996. - Вип.3. – С. 45–72

18. Петренюк А.Я. Об одном семействе инвариантов и новых неизоморфных схемах B(28,4,1) / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1984. – 10 с. - Деп. в УкрНИИНТИ, N 530 - Ук-Д84.

19. Петренюк А.Я. Обобщения преобразований, приводящих к неизоморфным тактическим конфигурациям / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1984. – 9 с. - Рус. - Деп. в УкрНИИНТИ 23.09.89, N 1560 - Ук-Д84.

20. Петренюк А.Я. Ознаки неізоморфності систем трійок Штейнера // Укр. мат. журн. – 1972. - 24, N 6. – С. 772 – 780.

21. Петренюк А.Я., Перечень совершенных 1-факторизаций порядка 12 ранга 4 / Гос. летная академия Украины. – Кировоград, 1997. – 21 с. – Рус. - Деп. в ГНТБ Украины 04.04.97, N 289 - Ук97.

22. Петренюк А.Я. Перечисление малых неизоморфных пентагональных упаковок // Кибернетика и системный анализ. – 1999. - № 6. – С. 72 – 78.

23. Петренюк А.Я. Перечисление неизоморфных гомогенных пентагональных упаковок // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1999. – С. 57 – 63.

24. Петренюк А.Я. Півобертові деревні факторизації повних графів // Укр. мат. журнал. - 2001. - 53, №5. – С. 710 – 716.

25. Петренюк А.Я. Применение инвариантов в комбинаторных исследованиях // Вопросы кибернетики: Тр. семинара по комбинаторной математике. - М.: Сов. радио, 1973. – С.129 – 136.

26. Петренюк А.Я. Про перелік кубічних розкладів повного графу K(10) // П'ята міжнар. наук. конф. ім. акад. М.Кравчука (16-18 травня 1996 р., Київ): Тези доп. - К., 1996. – С.332.

27. Petrenjuk L.P., Petrenjuk A.J. An enumeration method for nonisomorphic combinatorial designs // Annals of Discrete Mathematics. – 1980. – № 7. –
Р. 265–276.

28. Петренюк А.Я., Непорожнев И.П. Конструктивное перечисление систем групп пар и оглавленные системы троек Штейнера // Комбинаторный анализ. – М.: Изд-во Моск. ун-та. – 1972. - Вып.2. – С. 17–37; 1974. - Вып.3. - С. 28–42; 1980. - Вып.4. – С. 99–102.

29. Петренюк А.Я., Черновол А.С. Преобразование звездных покрытий графов посредством обращения звездных циклов / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1983. – 8 с. - Деп. в УкрНИИНТИ 22.06.83, N 558 - Ук-Д83.

30. Петренюк А.Я., Шнитер В.Ю. О строении графа H-преобразований 1-факторизаций порядка 10 // j-преобразования и комбинаторные свойства графов. - Препр. - Ин-т математики АН УССР. – К., 1978. – С. 34–48.

31. Петренюк В.І., Петренюк А.Я. Про новi Кiркмановi системи трiйок порядку 21 // Научные труды академии. - 1995. - Вып.1. – Гос. летная академия Украины. – С. 134 - 145.

32. Петренюк Л.П., Петренюк А.Я. К перечислению неизоморфных разложений графа K(10) на кубические факторы // Научные труды академии. – 1995. - Вып.1. – Гос. летная академия Украины. – С. 115 - 117.

33. Петренюк Л.П., Петренюк А.Я. К перечислению неизоморфных разложений графа K(10) на кубические факторы // Научные труды академии. – 1996. - Гос. летная академия Украины. – С. 69. – Рус. - Деп. в ГНТБ Украины 24.10.96, N 2125 - Ук96.

34. Петренюк Л.П., Петренюк А.Я. Метод H-преобразований в применении к киркмановым разрешениям штейнеровых систем / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1983. - 26 c. - Деп. в УкрНИИНТИ 01.09.83, N 994 - УкД83.

35. Петренюк Л.П., Петренюк А.Я. О конструктивном перечислении 12-вершинных кубических графов // Комбинаторный анализ. - 1974.- Вып.3.– С. 72–82 (испр. в вып. 4).

36. Петренюк Л.П., Петренюк А.Я. О неизоморфных B(25,4,1) и KST(21) / Кировоград. ин-т с.-х. машиностр. - Кировоград, 1983. - 9 с. - Деп. в УкрНИИНТИ 06.01.84, N 84 - УкД84.

37. Петренюк Л.П., Петренюк А.Я. Перечень десятивершинных однородных графов степени 4 // Вопросы кибернетики. – 1975. - Вып. 15: Тр. II Всесоюз. семинара по комбинаторной математике. – М., Сов. радио. – С. 71–75.

38. Петренюк Л.П., Петренюк А.Я. О перечислении совершенных 1-факторизаций полных графов // Кибернетика. – 1980. – № 1. – С. 6 – 8.

39. Петренюк Л.П., Петренюк А.Я. О семействе неизоморфных киркмановых разрешений одной штейнеровой системы троек // Комбинаторно-алгебраические методы в прикладной математике. - Горький, 1983. - Вып.5. – С. 176 – 192.

40. Петренюк Л.П., Петренюк А.Я. Перечисление кубических факторизаций графа K(1O) с попарно неизоморфными компонентами / Гос. летная академия Украины.– Кировоград, 1997.–186 с. - Деп. в ГНТБ Украины 18.06.97, N 377-Ук97.

41. Петренюк Л.П., Петренюк А.Я. Перечисление совершенных 1-факторизаций кубических и полных графов порядка 14 / Кировоградский ин-т с.-х. машиностр. - Кировоград, 1982. – 34 с. - Деп.в УкрНИИНТИ 22.07.82, N 3712, Ук-Д82.

42. Петренюк Л.П., Петренюк А.Я. Построение некоторых классов кубических графов и неизоморфность киркмановых систем троек // Комбинаторный анализ. – 1976. - Вып.4. – С. 73 – 77.

43. Petrenjuk A.J. A generalization of Kirkman triple systems / Державна льотна академія України. – Кіровоград, 2001. – 32 c. – Деп. в ДНТБ України 03.12.2001, N 184, Ук2001.

44. Petrenjuk A.J. Decomposing K(1O) into cubic graphs of order 6 // Bull. Inst. Combin. Appl. - 1994. – № 12. – С. 9 – 14.

45. Petrenjuk A.J. Enumerating decompositions of K(10) into isomorphic cubic factors // Свiтогляд. – 1998. - Вип.2. - Кіровоград, 1996. – С. 52 – 60.

46. Petrenjuk A.J. Enumeration of minimal tree decompositions of complete graphs // J.of Combin. Math. and Combin. Computing. - 1992. - № 12 – С. 197 – 199.

47. Petrenjuk A.J. Every tree from T[14,4] admits a T-factorization / Державна льотна академія України.– Кіровоград, 2001.– 21 с. - Деп. в ДНТБ України 23.06.2001, N 147, Ук2001.

48. Petrenjuk A.J. Nonisomorphic double star factorizations of order 12 // Наук. пр. академії: Під ред. Р.М.Макарова.– Кіровоград, Вид-во Державна льотна академія України, 1999. – Вип. 4, ч. 1. – С. 212 – 214.

49. Petrenjuk A.J. On the constructive enumeration of packings and coverings of index 1 // Discrete Mathematics. - 1989. - 77. – С. 237 – 254.

50. Petrenjuk A.J. On tree factorizations of K₁₀ // J.of Combin. Math. and Combin. Computing. - 2002. - 41. – Р. 193 - 202.

51. Petrenjuk A.J. On bicyclic tree factorizability over T[14,5] / Державна льотна академія України.- Кіровоград, 2001.- 18 c. – Деп. в ДНТБ України 23.06.2001, N 148 - Ук2001.