Метрична розмірність уніциклічних графів, які містять не більше однієї основної вершини

Анотація

Мінімальна підмножина $M\subset V$ така, що для будь-якої пари вершин $x, y$ графа $G$ існує така вершина $t$ з підмножини $M$, що виконується умова $d_G(t,x)\ne d_G(t,y)$, називається метричним базисом. Потужність цієї підмножини $M$ називається метричною розмірністю. Як відомо, повне дослідження метричної розмірності графів є NP-повною проблемою. Ми вводимо конструкцію часткового обплетення уніциклічних графів, за допомогою якої охарактеризовано уніциклічні графи метричної розмірності 2, які мають не більше однієї основної вершини.