Сильна метрична розмiрнiсть унiциклiчних графiв
Journal Title: Могилянський математичний журнал - Year 2018, Vol 1, Issue
Abstract
Вершина w простого зв’язного графа G сильно роздiляє двi вершини u i v цього графа, якщо виконується одна з двох рiвностей: dG(w, u) = dG(w, v) + dG(v, u) або dG(w, v) = dG(w, u) + dG(u, v). Множина S найменшої потужностi, елементи якої сильно роздiляють довiльну пару вершин графа G, називається сильним метричним базисом графа G. У загальному випадку пошук сильного метричного базису є NP-важкою проблемою. У цiй статтi знайдено формулу для обчислення сильної метричної розмiрностi унiциклiчних графiв, тобто графiв, що мають один цикл.
Authors and Affiliations
Mariia Matveieva
Keywords
Related Articles
- EP ID EP592842
- DOI 10.18523/2617-7080i2018p25-29
- Views 60
- Downloads 0
Сильна метрична розмiрнiсть унiциклiчних графiв
Вершина w простого зв’язного графа G сильно роздiляє двi вершини u i v цього графа, якщо виконується одна з двох рiвностей: dG(w, u) = dG(w, v) + dG(v, u) або dG(w, v) = dG(w, u) + dG(u, v). Множина S найменшої потужност...
Антиподальнi графи дiаметра 4
Метричний простiр (X, d) називається антиподальним, якщо для довiльної точки x iснує таке y, що для довiльної точки z множини X виконується рiвнiсть d(x, z) + d(z, y) = d(x, y). Вiдомими конструкцiями антиподальних графi...
Перiодичнi бiотопнi простори
У статтi введено узагальнення бiотопної метрики на нескiнченний випадок. Побудовано родину перiодичних бiотопних просторiв, елементами яких є перiодичнi {0, 1}-послiдовностi, перiоди яких є дiльниками супернатуральних чи...
Побудова коспектральних графiв вiдносно узагальненої матрицi сумiжностi
Спектральна теорiя графiв використовує власнi значення матриць, асоцiйованих iз графом, для визначення структурних властивостей графа. У статтi розглянуто спектр узагальненої матрицi сумiжностi. Графи з однаковим спектро...
Iнтерполяцiя випадкового поля для областi спостережень у виглядi системи вкладених прямокутникiв
Дослiджено задачу оцiнювання лiнiйних функцiоналiв вiд невiдомих значень однорiдного випадкового поля ξ(x, y) для областi K за спостереженнями поля ξ(x, y) в точках (x, y) ∈ Z2\K. Знайдено формули для обчислення середньо...