×

On unicyclic graphs of metric dimension 2 with vertices of degree 4. (English) Zbl 1421.05036

A vertex \(u\) of a connected, simple, finite, undirected graph \(G=(V,E)\) resolves vertices \(v_1\) and \(v_2\) of \(G\), if \(d(u,v_1)=d(u,v_2)\). A resolving set is an ordered vertex subset \(S\) of \(V\) such that every two distinct vertices of \(G\) are resolved by some vertex of \(S\). A resolving set of minimum cardinality is said to be a metric basis of \(G\). A metric dimension, \(\dim (G)\) of \(G\) is the cardinality of its metric basis. The authors characterize all unicyclic graphs of metric dimension \(2\) with vertices of degree \(4\) by introducing unispider and semiunispider graphs and their knittings.

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: MNR

References:

[1] Frank Harary, Robert A. Melter, “On the metric dimension of a graph”, Ars Comb., 2 (1976), 191-195 · Zbl 0349.05118
[2] P. J. Slater, “Leaves of trees”, Congress. Numer., 14 (1975), 549-559
[3] M. Johnson, “Structure-activity maps for visualizing the graph variables arising in drug design”, J.Biopharm. Stat., 3:2 (1993), 203-236 · Zbl 0800.92106
[4] Robert A. Melter, I. Tomescu, “Metric bases in digital geometry”, Comput. Vision, Graph. Image Process, 25:1 (1984), 113-121 · Zbl 0591.51023
[5] A.Sebo, E.Tannier, “On metric generators of graphs”, Math. of Operations Research, 29 (2004), 383-393 · Zbl 1082.05032
[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 · Zbl 0411.68039
[7] S. Khuller, B. Raghavachari and A. Rosenfeld, “Landmarks in graphs”, Disc. Appl. Math., 70 (1996), 217-229 · Zbl 0865.68090
[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 · Zbl 0958.05042
[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 · Zbl 1177.05121
[10] Marharyta Dudenko, Bogdana Oliynyk, “On unicyclic graphs of metric dimension 2”, Algebra Discrete Math., 23:2 (2017), 216-222 · Zbl 1377.05046
[11] Marharyta Dudenko, “Metric dimension of unicyclic graphs with at most one main vertex”, Visnyk of Lviv University, 83 (2017), 189-195 · Zbl 1377.05046
[12] Reinhard Diestel, Graph Theory, ed. 3rd ed., Springer-Verlag, Berlin-New York, 2005 · Zbl 1074.05001
[13] Marharyta Dudenko, “Unicyclic graphs with metric dimension \(2\)”, Nauk. Zapysky NaUKMA, 165 (2015), 7-10 · Zbl 1377.05046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.