Сильна метрична розмірність уніциклічних графів
Loading...
Date
2018
Authors
Матвеєва, Марія
Journal Title
Journal ISSN
Volume Title
Publisher
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в, що мають один цикл.
C 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 unicycl
C 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 unicycl
Description
Keywords
метрична розмiрнiсть графiв, сильна метрична розмiрнiсть, дерево, унiциклiчний граф, стаття, metric dimension of a graph, strong metric dimension of a graph, tree, unicyclic graph
Citation
Матвеєва М. М. Сильна метрична розмірність уніциклічних графів / Матвеєва М. М. // Могилянський математичний журнал : науковий журнал. - 2018. - Т. 1. - С. 25-29.