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

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

Marharyta Dudenko

Анотація


Найменшу за потужн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д способу вилучення ребра.

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


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

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

PDF

Посилання


L. M. Blumenthal, Theory and applications of distance geometry (Clarendon Press, Oxford, 1953).

P. J. Slater, “Leaves of trees”, Congr. Number. 14, 549–559 (1975).

F. Harary, R. A. Melter, “On the the metric dimension of a graph”, Ars Combinatoria. 2, 191–195 (1976).

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

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

Chvatal V. “Mastermind”, Combinatorica. 3., 325–329 (1983).

M. R. Garey, D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness (Freeman, New York, 1979).

B. Shanmukha, B. Sooryanarayana, K. S. Harinath, “Metric dimension of wheels”, Far East J. Appl. Math. 8 (3), 217–229 (2002).

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

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

M. A. Dudenko, “Unitsyklichni hrafy metrychnoi rozmirnosti 2”, Naukovi zapysky NaUKMA. 165: Fizyko-matematychni nauky, 7–10 (2015).

M. Dudenko, B. Oliynyk, “On unicyclic graphs of metric dimension 2”, Algebra and Discrete Math. 23 (2), 216–222 (2017).

M. A. Dudenko, “Metrychna rozmirnist unitsyklichnykh hrafiv, shcho mistiat ne bilshe odniiei osnovnoi vershyny”, Visnyk Lvivskoho universytetu. 83: Mekhaniko-matematychni nauky, 189–195 (2017).

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).

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






Copyright (c) 2019 Marharyta Dudenko

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