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

Simple item page
dc.contributor.authorМатвеєва, Марія
dc.date.accessioned2018-12-13T15:45:09Z
dc.date.available2018-12-13T15:45:09Z
dc.date.issued2018
dc.description.abstractВершина 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в, що мають один цикл.uk_UA
dc.description.abstractC GRAPHS Let G be a simple connected graph. A metric dimension s of a graph G is the cardinality of the smallest subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. A vertex w of graph G strongly resolves two vertices u, v ∈ V (G) if one of the equalities hold: dG(w, u) = dG(w, v) + dG(v, u) or dG(w, v) = dG(w, u) + dG(u, v). In other words, a vertex w in a graph G strongly resolves a pair of vertices u, v if there exists a shortest w-u path containing v or a shortest w-v path containing u in G. A set S of minimum cardinality whose elements strongly resolve any pair of vertices of G is called a strong metric basis of graph G. Typical, a metric dimension of a graph G is not equal to a strong metric dimension of a graph G. A metric dimension as a graph parameter and strong metric dimension have numerous applications. In general, a search of metric dimension and strong metric dimension is NP-hard problem. But for some families of graphs, for example, for trees, there is a polynomial algorithm for that searching. This paper characterizes such trees that a metric dimension equals a strong metric dimension. In this article, we use properties of strong metric basis of trees and cycles to obtain a closed formula for calculating a strong metric dimension of unicyclic graphs, namely graphs that have only one cycle. We say that leaf u which lies out of the cycle is projected onto vertex v that lies in the cycle if deg(v) ≥ 3 and v is connected to u through the shortest path. A strong metric dimension depends on the number of inner vertexes of the cycle, their position in it, and the number of leaves that are projected onto each inner vertex of the cycle. Note that now there is no closed formula for calculating metric dimension of unicyclen_US
dc.identifier.citationМатвеєва М. М. Сильна метрична розмірність уніциклічних графів / Матвеєва М. М. // Могилянський математичний журнал : науковий журнал. - 2018. - Т. 1. - С. 25-29.uk_UA
dc.identifier.issn2617-7080
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/14915
dc.identifier.urihttps://doi.org/10.18523/2617-7080i2018p25-29
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журнал : науковий журнал. - 2018. - Т. 1uk_UA
dc.statusfirst publisheduk_UA
dc.subjectметрична розмiрнiсть графiвuk_UA
dc.subjectсильна метрична розмiрнiстьuk_UA
dc.subjectдеревоuk_UA
dc.subjectунiциклiчний графuk_UA
dc.subjectстаттяuk_UA
dc.subjectmetric dimension of a graphen_US
dc.subjectstrong metric dimension of a graphen_US
dc.subjecttreeen_US
dc.subjectunicyclic graphen_US
dc.titleСильна метрична розмірність уніциклічних графівuk_UA
dc.title.alternativeStrong metric dimensions of unicyclic graphsen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Matveieva_Sylna_metrychna_rozmirnist_unitsyklichnykh_hrafiv.pdf
Size:
154.85 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 1