DOI: https://doi.org/10.18523/2617-7080i2018p25-29

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

Mariia Matveieva

Анотація


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

Ключові слова


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

Повний текст:

PDF

Посилання


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






Copyright (c) 2018 Mariia Matveieva

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.