Сильна метрична розм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 74
- Downloads 0
Антиподальн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йного розвитку. Таким, зокрема, є поняття складної динамiчної системи з притягальн...
Алгоритм обчислень у силовських 2-пiдгрупах знакозмiнних груп за допомогою системи комп’ютерної алгебри GAP
У статтi наведено алгоритм перевiрки, чи є певна множина елементiв S мiнiмальною системою твiрних для силовської 2-пiдгрупи знакозмiнної групи Syl2(A2n), за допомогою системи комп’ютерної алгебри GAP. Для невеликих n (n...
Скiнченнi локальнi майже-кiльця
У статтi здiйснено огляд сучасного стану дослiдження скiнченних локальних майже-кiлець, а саме їх похiдних структур — адитивної та мультиплiкативної груп. Наведено класифiкацiю локальних майжекiлець, порядок яких не пере...
Сильна метрична розм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 найменшої потужност...