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

Автор(и)

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

DOI:

https://doi.org/10.18523/2617-70802201933-40

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

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

Анотація

Найменшу за потужнiстю множину M ∈ V скiнченного графа G = (V, E) таку, що для будь-якої пари вершин u, v ∈ V iснує принаймнi одна вершина t ∈ M, для якої має мiсце нерiвнiсть dG(t, v) 6= dG(t, u), називають метричним базисом, а потужнiсть множини M – метричною розмiрнiстю. Оскiльки, як вiдомо, пошук метричної розмiрностi для довiльного графа є NP-важкою проблемою, то пошук метричної розмiрностi графiв обмежують пошуком для певних родин графiв. Для унiциклiчних графiв, тобто графiв, що мiстять рiвно один цикл, пiсля вилучення ребра можна отримати дерево. Метою статтi є встановлення зв’язку мiж унiциклiчним графом, що має метричну розмiрнiсть 2, та метричними розмiрностями його кiстякових дерев залежно вiд способу вилучення ребра.

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

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

кандидат фiзико-математичних наук, старший викладач кафедри математики Нацiонального унiверситету «Києво-Могилянська академiя».

Сфера наукових iнтересiв — дискретна математика, теорiя графiв

m.dudenko@ukma.edu.ua

Посилання

  1. L. M. Blumenthal, Theory and applications of distance geometry (Clarendon Press, Oxford, 1953).
  2. P. J. Slater, “Leaves of trees”, Congr. Number. 14, 549–559 (1975).
  3. F. Harary, R. A. Melter, “On the the metric dimension of a graph”, Ars Combinatoria. 2, 191–195 (1976).
  4. G. Chartrand, L. Eroh, M. A. Johnson, “Resolvability in graphs and the metric dimension of a graph”, Discrete Appl. Math. 105, 99–113 (2000). doi: https://doi.org/10.1016/s0166-218x(00)00198-0
  5. Z. Beerliova, F. Eberhard, T. Erlebach, A Hall, M. Hoffmann, M. Mihal’ak, L. S. Ram, “Network discovery and verification”, IEEE J. Sel. Areas Commun. 24 2168–2181 (2006). doi: https://doi.org/10.1109/jsac.2006.884015
  6. Chvatal V. “Mastermind”, Combinatorica. 3., 325–329 (1983).
  7. M. R. Garey, D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness (Freeman, New York, 1979).
  8. B. Shanmukha, B. Sooryanarayana, K. S. Harinath, “Metric dimension of wheels”, Far East J. Appl. Math. 8 (3), 217–229 (2002).
  9. S. Khuller, B. Raghavachari, A. Rosenfeld, “Landmarks in graphs”, Disc. Appl. Math. 70, 217—229 (1996). doi: https://doi.org/10.1016/0166-218x(95)00106-2
  10. L. Eroh, P. Feit, C. X. Kang, Y. Eunjeong, “The effect of vertex or edge deletion on the metric dimension of graphs”, Journal of Combinatorics. 6 (4), 433–444 (2015). doi: https://doi.org/10.4310/joc.2015.v6.n4.a2
  11. M. A. Dudenko, “Unitsyklichni hrafy metrychnoi rozmirnosti 2”, Naukovi zapysky NaUKMA. 165: Fizyko-matematychni nauky, 7–10 (2015).
  12. M. Dudenko, B. Oliynyk, “On unicyclic graphs of metric dimension 2”, Algebra and Discrete Math. 23 (2), 216–222 (2017).
  13. M. A. Dudenko, “Metrychna rozmirnist unitsyklichnykh hrafiv, shcho mistiat ne bilshe odniiei osnovnoi vershyny”, Visnyk Lvivskoho universytetu. 83: Mekhaniko-matematychni nauky, 189–195 (2017).
  14. M. Dudenko, B. Oliynyk, “On unicyclic graphs of metric dimension 2 with vertices of degree 4”, Algebra and Discrete Math. 26 (2), 256–269 (2018).
  15. A. Sebo, E. Tannier, “On Metric Generators of Graphs”, Mathematics of Operations Research. 29 (2), 383–393 (2004). doi: https://doi.org/10.1287/moor.1030.0070

##submission.downloads##

Як цитувати

[1]
Dudenko, M. 2019. Метрична розмiрнiсть кiстякових дерев унiциклiчних графiв. Могилянський математичний журнал. 2, (Груд 2019), 33–40. DOI:https://doi.org/10.18523/2617-70802201933-40.