International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 38, Pages 1997-2017

Conditional resolvability in graphs: a survey

Varaporn Saenpholphat1 and Ping Zhang2

1Department of Mathematics, Srinakharinwirot University, Bangkok 10110, Thailand
2Department of Mathematics, Western Michigan University, Kalamazoo 49008, MI, USA

Received 29 November 2003

Copyright © 2004 Varaporn Saenpholphat and Ping Zhang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


For an ordered set W={w1,w2,,wk} of vertices and a vertex v in a connected graph G, the code of v with respect to W is the k-vector cW(v)=(d(v,w1),d(v,w2),,d(v,wk)), where d(x,y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct codes with respect to W. The minimum cardinality of a resolving set for G is its dimension dim(G). Many resolving parameters are formed by extending resolving sets to different subjects in graph theory, such as the partition of the vertex set, decomposition and coloring in graphs, or by combining resolving property with another graph-theoretic property such as being connected, independent, or acyclic. In this paper, we survey results and open questions on the resolving parameters defined by imposing an additional constraint on resolving sets, resolving partitions, or resolving decompositions in graphs.