International Journal of Mathematics and Mathematical Sciences · 2004 · 69 citations · 21 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationCoding TheoryDirected Acyclic GraphsGraph AlgorithmsGraph ColoringGraph TheoryCardinality EstimationComputational Complexity Of Graph AlgorithmsGraph ConstraintsOpen QuestionsVertex DistanceVertex Ordering
For an ordered set W = { w 1 , w 2 , …, w k } of vertices and a vertex v in a connected graph G , the code of v with respect to W is the k ‐vector c W ( v ) = ( d ( v , w 1 ), d ( v , w 2 ), …, d ( v , w k )), 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.
21
Resolvability in graphs and the metric dimension of a graph
Gary Chartrand, Linda Eroh, Mark A. Johnson et al. · Discrete Applied Mathematics · 2000 · 982 citations
The partition dimension of a graph
Gary Chartrand, Ebrahim Salehi, P. Zhang · Aequationes Mathematicae · 2000 · 249 citations
Domination and location in acyclic graphs
Peter J. Slater · Networks · 1987 · 206 citations
On k-dimensional graphs and their bases
Peter S. Buczkowski, Gary Chartrand, Christopher Poisson et al. · Periodica Mathematica Hungarica · 2003 · 167 citations