Weak Total Resolvability In Graphs

Katrin Casel, et al. "Weak Total Resolvability In Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 185-210. <http://eudml.org/doc/276978>.

@article{KatrinCasel2016,
abstract = {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.},
author = {Katrin Casel, Alejandro Estrada-Moreno, Henning Fernau, Juan Alberto Rodríguez-Velázquez},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {metric dimension; resolving set; weak total metric dimension; weak total resolving set; adjacency dimension; graph operations},
language = {eng},
number = {1},
pages = {185-210},
title = {Weak Total Resolvability In Graphs},
url = {http://eudml.org/doc/276978},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Katrin Casel
AU - Alejandro Estrada-Moreno
AU - Henning Fernau
AU - Juan Alberto Rodríguez-Velázquez
TI - Weak Total Resolvability In Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 185
EP - 210
AB - 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.
LA - eng
KW - metric dimension; resolving set; weak total metric dimension; weak total resolving set; adjacency dimension; graph operations
UR - http://eudml.org/doc/276978
ER -