Сильна метрична розмiрнiсть унiциклiчних графiв
DOI:
https://doi.org/10.18523/2617-7080i2018p25-29Ключові слова:
метрична розм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 найменшої потужностi, елементи якої сильно роздiляють довiльну пару вершин графа G, називається сильним метричним базисом графа G. У загальному випадку пошук сильного метричного базису є NP-важкою проблемою. У цiй статтi знайдено формулу для обчислення сильної метричної розмiрностi унiциклiчних графiв, тобто графiв, що мають один цикл.Посилання
- Slater, P. J. (1975). Leaves of trees. Congressus Numerantium, 14, 549–559.
- Slater, P. J., & Melter, R. A. (1976). On the metric dimension of a graph. Ars Combinatoria, 2, 191–195.
- Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co.
- Chartrand, G., Eroh, L., Johnson, M. A., & Oellerman, O. R. (2000). Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105, 99–113. https://doi.org/10.1016/s0166-218x(00)00198-0
- Jannesari, M., & Omoomi, B. (2014). Characterization of n-vertex graphs with metric dimension n-3. Mathematica Bohemicas, (pp. 1–23).
- Poisson, C., & Zhang, P. (2002). The metric dimension of unicyclic graphs. J. Combin. Math. Combin. Comput, 40, 17–32.
- Dudenko, M., & Oliynyk, B. (2017). On unicyclic graphs of metric dimension 2. Algebra and Discrete Mathematics, 32, 216–222.
- Oellermann, O. R., & Peters-Fransen, J. (2007). The strong metric dimension of graphs and digraphs. Discrete Applied Mathematics, 155, 356–364. https://doi.org/10.1016/j.dam.2006.06.009
- Yero, I. G., & Rodriguez-Velazquez, J. A. (2010). A note on the partition dimension of cartesian product graphs. Applied Mathematics and Computation, 217, 3571–3574. https://doi.org/10.1016/j.amc.2010.08.038
- Bodnarchuk, Yu. V., & Oliinyk, B. V. (2007). Osnovy dyskretnoi matematyky : navch. posib. Kyiv: Vyd. dim "Kyievo-Mohylianska akademiia".
- Kuziak, D., Yero, I. G., & Rodriguez-Velayquez, J. A. (2015). On the strong metric dimension of the strong products of graphs. Open Math., 13, 67–74. https://doi.org/10.1515/math-2015-0007
- Sebo, A., & Tannier, E. (2004). On metric generators of graphs. Mathematics of Operations Research, 29, 383–393. https://doi.org/10.1287/moor.1030.0070
##submission.downloads##
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2018 Mariia Matveieva
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, погоджуються з такими умовами:
а) Автори зберігають за собою авторські права на твір на умовах ліцензії Creative Commons Attribution License CC BY 4.0, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.
б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.
в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)
г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).