The thesis is devoted to the study of the metric dimension of unicyclic graphs, in particular the characterization of all unicyclic graphs with a metric dimension 2, and a description of the relationships between the metric dimension of unicyclic graphs and their corresponding trees.
In the thesis all unicyclic graphs, i.e. graphs with exactly one cycle, with metric dimension 2 are completely characterized.
Let G be a unicyclic graph, and $\widehat{G}$ be its cycle. It is shown that an arbitrary unicyclic graph with metric dimension 2 does not contain any vertex of degree greater than 3 outside the cycle, i.e. for any v from $V(G) \setminus V(\widehat{G})$ $deg v \leq 3$. Define a main vertex of a unicyclic graph to be a degree-3 vertex $v \in V(\widehat{G})$ with the property that the component of $G \setminus E(\widehat{G})$ containing v has a vertex of degree 3. We prove that a unicyclic graph of metric dimension 2 has at most two main vertices.
At first, all unicyclic graphs with vertices of degree at most 3 are characterized. The concept of basic and minor graphs, as well as the construction of knitting and full knitting of graphs, was introduced. It was proved that the unicyclic graph with vertices of degree at most 3, is either a basic, or a full knitting of the basic graph, or a minor graph, or a knitting of a minor graph.
It was proved that unicyclic graph with metric dimension 2 can not contain vertices of degree 5, therefore the limitation that the maximum degree of any vertex in a cycle does not exceed 4 was given. Moreover, such vertices can be at most two and only in an odd graph.
The answer to the question how the vertices of degree 4 can be located in the cycle of graph and can they be the main vertices were given. For this purpose unispider and semiunispider graphs were presented and was shown that if an odd unicyclic graph $G$ has two main vertices and two vertices of degree 4, then these vertices coincide. If the graph G contains two main vertices and one vertex of degree 4, then one of the main vertices is the vertex of degree 4. Conversely, if the graph G contains two vertices of degree 4 and one main vertex, then one of the vertices of degree 4 is the main one. If, for graph G, one vertex is the main vertex and one has degree 4, then either these vertices coincide, or are arranged in a cycle at a distance k, where $|V(\widehat{G})|=2k + 1$.
For such graphs, the structure of knitting can also be used. It turns out that a unicyclic graph G with vertices of degree 4 has $ dim (G) = 2 $ if and only if G is a unispider graph or knitting of some unispider graph G, semiunispider graph or knitting of some semiunispider graph.
Thus, the necessary and sufficient conditions in which the unicyclic graph with vertices of degree 4 has a metric dimension 2 were formulated.
Also in the thesis the connection between the metric dimension of unicyclic graphs and the metric dimension of the trees formed of the unicyclic graphs, or vice versa, depending on the method of adding or deleting the edge was considered. The types of connections in which the metric dimension of the obtained unicyclic graph is equal to 2 were given, as well as the types of connections in which the metric dimension of the obtained unicyclic graph is equal to 3 were described. For this purpose, the concept of constructed and leaf-constructed graphs was introduced.
It was also showed the relationship between the metric dimension of a unicyclic graph and the metric dimension of its skeletal tree. Since the corresponding skeletal tree for the graph is determined ambiguously, depending on the method of deleting the edge to obtain that tree, its metric dimension may also change. So conditions under which the skeletal tree of a unicyclic graph G with $dim (G) = 2$ has a metric dimension from 1 to 4 were described.
