Geodesic
On unicyclic graphs of metric dimension~2 with vertices of degree~4
Algebra and discrete mathematics, Tome 26 (2018) no. 2, pp. 256-269.

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that if $G$ is a unicyclic graph with metric dimension $2$ and $\{a,b\}$ is a metric basis of $G$ then the degree of any vertex $v$ of $G$ is at most $4$ and degrees of both $a$ and $b$ are at most $2$. The constructions of unispider and semiunispider graphs and their knittings are introduced. Using these constructions all unicyclic graphs of metric dimension $2$ with vertices of degree $4$ are characterized.
Keywords: graph, metric dimension
Mots-clés : distance, unicyclic graph. 
@article{ADM_2018_26_2_a4,
     author = {M. Dudenko and B. Oliynyk},
     title = {On unicyclic graphs of metric dimension~2 with vertices of degree~4},
     journal = {Algebra and discrete mathematics},
     pages = {256--269},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2018_26_2_a4/}
}
TY  - JOUR
AU  - M. Dudenko
AU  - B. Oliynyk
TI  - On unicyclic graphs of metric dimension~2 with vertices of degree~4
JO  - Algebra and discrete mathematics
PY  - 2018
SP  - 256
EP  - 269
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2018_26_2_a4/
LA  - en
ID  - ADM_2018_26_2_a4
ER  - 
%0 Journal Article
%A M. Dudenko
%A B. Oliynyk
%T On unicyclic graphs of metric dimension~2 with vertices of degree~4
%J Algebra and discrete mathematics
%D 2018
%P 256-269
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2018_26_2_a4/
%G en
%F ADM_2018_26_2_a4
M. Dudenko; B. Oliynyk. On unicyclic graphs of metric dimension~2 with vertices of degree~4. Algebra and discrete mathematics, Tome 26 (2018) no. 2, pp. 256-269. http://geodesic.mathdoc.fr/item/ADM_2018_26_2_a4/

[1] Frank Harary, Robert A. Melter, “On the metric dimension of a graph”, Ars Comb., 2 (1976), 191–195 | MR | Zbl

[2] P. J. Slater, “Leaves of trees”, Congress. Numer., 14 (1975), 549–559 | MR

[3] M. Johnson, “Structure-activity maps for visualizing the graph variables arising in drug design”, J.Biopharm. Stat., 3:2 (1993), 203–236 | DOI | MR | Zbl

[4] Robert A. Melter, I. Tomescu, “Metric bases in digital geometry”, Comput. Vision, Graph. Image Process, 25:1 (1984), 113–121 | DOI | MR | Zbl

[5] A.Sebo, E.Tannier, “On metric generators of graphs”, Math. of Operations Research, 29 (2004), 383–393 | DOI | MR | Zbl

[6] Michael R. Garey, David S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco, 1979 | MR | Zbl

[7] S. Khuller, B. Raghavachari and A. Rosenfeld, “Landmarks in graphs”, Disc. Appl. Math., 70 (1996), 217–229 | DOI | MR | Zbl

[8] Gary Chartrand, Linda Eroh, Mark A. Johnson, Ortrud R. Oellermann, “Resolvability in graphs and the metric dimension of a graph”, Discrete Appl. Math., 105:1–3 (2000), 99–113 | MR | Zbl

[9] G. Sudhakara, A. R. Hemanth Kumar, “Graphs with metric dimension two—a characterization”, Adv. and Appl. in Disc. Math., 4:2 (2009), 169–186 | MR | Zbl

[10] Marharyta Dudenko, Bogdana Oliynyk, “On unicyclic graphs of metric dimension 2”, Algebra Discrete Math., 23:2 (2017), 216–222 | MR | Zbl

[11] Marharyta Dudenko, “Metric dimension of unicyclic graphs with at most one main vertex”, Visnyk of Lviv University, 83 (2017), 189–195

[12] Reinhard Diestel, Graph Theory, ed. 3rd ed., Springer-Verlag, Berlin–New York, 2005 | MR | Zbl

[13] Marharyta Dudenko, “Unicyclic graphs with metric dimension $2$”, Nauk. Zapysky NaUKMA, 165 (2015), 7–10