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

Автор(и)

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

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.