Weak Total Resolvability In Graphs

• Autorzy: Katrin Casel , Alejandro Estrada-Moreno , Henning Fernau , Juan Alberto Rodríguez-Velázquez
• Języki publikacji: EN

Abstrakty

EN

A vertex v ∈ V (G) is said to distinguish two vertices x, y ∈ V (G) of a graph G if the distance from v to x is di erent from the distance from v to y. A set W ⊆ V (G) is a total resolving set for a graph G if for every pair of vertices x, y ∈ V (G), there exists some vertex w ∈ W − {x, y} which distinguishes x and y, while W is a weak total resolving set if for every x ∈ V (G)−W and y ∈ W, there exists some w ∈ W −{y} which distinguishes x and y. A weak total resolving set of minimum cardinality is called a weak total metric basis of G and its cardinality the weak total metric dimension of G. Our main contributions are the following ones: (a) Graphs with small and large weak total metric bases are characterised. (b) We explore the (tight) relation to independent 2-domination. (c) We introduce a new graph parameter, called weak total adjacency dimension and present results that are analogous to those presented for weak total dimension. (d) For trees, we derive a characterisation of the weak total (adjacency) metric dimension. Also, exact figures for our parameters are presented for (generalised) fans and wheels. (e) We show that for Cartesian product graphs, the weak total (adjacency) metric dimension is usually pretty small. (f) The weak total (adjacency) dimension is studied for lexicographic products of graphs.

Słowa kluczowe

EN

metric dimension; resolving set; weak total metric dimension; weak total resolving set; adjacency dimension; graph operations

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C76: Graph operations (line graphs, products, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 185-210

Daty

wydano

2016-02-01

otrzymano

2014-10-20

poprawiono

2015-05-29

zaakceptowano

2015-05-29

online

2016-01-19

Twórcy

autor

Katrin Casel

• FB 4-Abteilung Informatikwissenschaften, Universität Trier, 54286 Trier, Germany

autor

Alejandro Estrada-Moreno

• Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Spain

autor

Henning Fernau

• FB 4-Abteilung Informatikwissenschaften, Universität Trier, 54286 Trier, Germany

autor

Juan Alberto Rodríguez-Velázquez

• Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Spain

Bibliografia

• [1] R.C. Brigham, G. Chartrand, R.D. Dutton and P. Zhang, Resolving domination in graphs, Math. Bohem. 128 (2003) 25–36.
• [2] G. Chartrand, V. Saenpholphat and P. Zhang, The independent resolving number of a graph, Math. Bohem. 128 (2003) 379–393.
• [3] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Ed. (CRC Press, 2011).
• [4] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
• [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998).
• [6] I. Javaid, F. Iftikhar and M. Salman, Total resolvability in graphs, Middle-East Journal of Scientific Research 11 (2012) 1649–1658.
• [7] F. Okamoto, B. Phinezy and P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (2010) 239–255.
• [8] A. Sebö and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383–393. doi:10.1287/moor.1030.0070[Crossref]
• [9] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.

Identyfikatory

DOI

10.7151/dmgt.1853