Метрична розм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.

Номер

Том 2 (2019): Могилянський Математичний Журнал

Розділ

Статті

Ліцензія

Авторське право (c) 2019 Marharyta Dudenko

Creative Commons License

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

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

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

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

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

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