Сильна метрична розмiрнiсть унiциклiчних графiв

Автор(и)

  • Mariia Matveieva Національний університет «Києво-Могилянська академія», Ukraine

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в, що мають один цикл.

Біографія автора

Mariia Matveieva, Національний університет «Києво-Могилянська академія»

Студентка 3-го року навчання бакалаврської програми «Прикладна математика» Нацiонального унiверситету «Києво-Могилянська академiя». Сфера наукових iнтересiв -
теорiя графiв.

Посилання

  1. Slater, P. J. (1975). Leaves of trees. Congressus Numerantium, 14, 549–559.
  2. Slater, P. J., & Melter, R. A. (1976). On the metric dimension of a graph. Ars Combinatoria, 2, 191–195.
  3. 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.
  4. 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
  5. Jannesari, M., & Omoomi, B. (2014). Characterization of n-vertex graphs with metric dimension n-3. Mathematica Bohemicas, (pp. 1–23).
  6. Poisson, C., & Zhang, P. (2002). The metric dimension of unicyclic graphs. J. Combin. Math. Combin. Comput, 40, 17–32.
  7. Dudenko, M., & Oliynyk, B. (2017). On unicyclic graphs of metric dimension 2. Algebra and Discrete Mathematics, 32, 216–222.
  8. 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
  9. 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
  10. Bodnarchuk, Yu. V., & Oliinyk, B. V. (2007). Osnovy dyskretnoi matematyky : navch. posib. Kyiv: Vyd. dim "Kyievo-Mohylianska akademiia".
  11. 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
  12. 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##

Як цитувати

[1]
Matveieva, M. 2018. Сильна метрична розмiрнiсть унiциклiчних графiв. Могилянський математичний журнал. 1, (Груд 2018), 25–29. DOI:https://doi.org/10.18523/2617-7080i2018p25-29.

Номер

Том 1 (2018): Могилянський математичний журнал

Розділ

Статті

Ліцензія

Авторське право (c) 2018 Mariia Matveieva

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з такими умовами:

а) Автори зберігають за собою авторські права на твір на умовах ліцензії Creative Commons Attribution License CC BY 4.0, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.

б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.

в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)

г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).