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

dc.contributor.authorДуденко, Маргарита
dc.date.accessioned2019-12-09T23:35:24Z
dc.date.available2019-12-09T23:35:24Z
dc.date.issued2019
dc.description.abstractНайменшу за потужн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д способу вилучення ребраuk_UA
dc.description.abstractThe smallest subset M ⊂ V of a graph G = (V,E) such that for any pair u,v ∈ V there exists at least one vertex t ∈ M with dG(t,v) 6= dG(t,u), is called a metric basis of G, and its cardinality |M| is called the metric dimension of G and denoted by dim(G). Since it is known that finding the metric dimension of a graph is NP-hard problem, finding the metric dimension of a graph is usually carried out in certain directions such as description of graph classes for which the metric dimension can be found in polynomial time and calculation of the metric dimension of certain, well-known families of graphs (such as grid graphs, wheels, etc.). One of these areas of research deals with characterization of graph families having a constant metric dimension. In particular, it has been proven that a graph has the metric dimension 1 if and only if it is a path. It is also known that metric dimensions of the cycle Cn, the complete graph Kn and the complete bipartite graph Ks,t are equal to 2, n−1 and s + t−2, respectively. Another area of research on the metric bases of graphs is the finding the metric dimension of graphs obtained by operations on graphs whose metric bases are known. In this paper, we present the relationship between a unicyclic graph (a graph with exactly one cycle) with metric dimension 2 and the metric dimension of its spanning trees. Since the corresponding spanning trees for a graph are determined ambiguously, depending on the method of deleting the edge to obtain such a tree, its metric dimension may also change. The present paper describes conditions under which a spanning tree of a unicyclic graph G with dim(G) = 2 has the metric dimension from 1 to 4.en_US
dc.identifier.citationДуденко М. А. Метрична розмiрнiсть кiстякових дерев унiциклiчних графiв / Маргарита Дуденко // Могилянський математичний журнал. - 2019. - Т. 2. - С. 33-40.uk_UA
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/16772
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журналuk_UA
dc.statusfirst publisheduk_UA
dc.subjectметрикаuk_UA
dc.subjectунiциклiчний графuk_UA
dc.subjectметрична розмiрнiстьuk_UA
dc.subjectметричний базисuk_UA
dc.subjectкiстякове деревоuk_UA
dc.subjectвiдстаньuk_UA
dc.subjectстаттяuk_UA
dc.subjectmetricen_US
dc.subjectunicyclic graphen_US
dc.subjectmetric dimensionen_US
dc.subjectmetric basisen_US
dc.subjectspanning treeen_US
dc.subjectdistanceen_US
dc.subjectarticleen_US
dc.titleМетрична розмiрнiсть кiстякових дерев унiциклiчних графiвuk_UA
dc.title.alternativeMetric dimension of skeletal trees of unicyclic graphsen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Dudenko_Metrychna_rozmirnist_kistiakovykh_derev_unitsyklichnykh_hrafiv.pdf
Size:
566.88 KB
Format:
Adobe Portable Document Format
Description:
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:
Collections