Дуденко М. А. Метричні базиси графів

Дисертаційну роботу присвячено вивченню метричних базисів і метричної розмірності уніциклічних графів та опису зв'язків між метричною розмірністю уніциклічних графів та відповідних їм дерев. У роботі повністю охарактеризовано уніциклічні графи, що мають метричну розмірність 2 і описано їх структуру. Зокрема, показано, що в довільного такого графа не існує поза циклом вершини степеня більшого, ніж 3, а максимальний степінь вершин в циклі не перевищує 4 і лише в непарному уніциклічному графі. Для повної характеризації уніциклічних графів, що мають метричну розмірність 2, введено поняття базисного та мінорного графів, графів типу ``павучок'' та ``напівпавучок'', а також конструкції обплетення і повного обплетення вказаних графів. Описано зв'язок між метричними розмірностями дерева і побудованого з нього уніциклічного графа та знайдено метричну розмірність кістякових дерев уніциклічних графів, метричний базис яких містить два елементи.