Conditional resolvability in graphs: a survey
---
paper_title: Resolvability in graphs and the metric dimension of a graph

paper_content:

Abstract For an ordered subset W={w1,w2,…,wk} of vertices in a connected graph G and a vertex v of G, the metric representation of v with respect to W is the k-vector r(v | W)=(d(v,w 1 ) , d(v,w2),…,d(v,wk)). The set W is a resolving set for G if r(u | W)=r(v | W) implies that u=v for all pairs u,v of vertices of G. The metric dimension dim(G) of G is the minimum cardinality of a resolving set for G. Bounds on dim(G) are presented in terms of the order and the diameter of G. All connected graphs of order n having dimension 1,n−2, or n−1 are determined. A new proof for the dimension of a tree is also presented. From this result sharp bounds on the metric dimension of unicyclic graphs are established. It is shown that dim(H)⩽dim(H×K2)⩽dim(H)+1 for every connected graph H. Moreover, it is shown that for every positive real number e, there exists a connected graph G and a connected induced subgraph H of G such that dim(G)/dim(H)
---
paper_title: Resolvability and the upper dimension of graphs

paper_content:

Abstract For an ordered set W = { w 1 , w 2 ,…, w k } of vertices and a vertex v in a connected graph G , the (metric) representation of v with respect to W is the k -vector r ( v | W ) = ( 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 representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented. A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim( G ). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim + ( G ). The resolving number res( G ) of a connected graph G is the minimum k such that every k -set W of vertices of G is also a resolving set of G . Then 1 ≤ dim( G ) ≤ dim + ( G ) ≤ res( G ) ≤ n − 1 for every nontrivial connected graph G of order n . It is shown that dim + ( G ) = res( G ) = n − 1 if and only if G = K n , while dim + ( G ) = res( G ) = 2 if and only if G is a path of order at least 4 or an odd cycle. The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a , b of integers with 2 ≤ a ≤ b , there exists a connected graph G with dim( G ) = dim + ( G ) = a and res( G ) = b . Also, for every positive integer N , there exists a connected graph G with res( G ) − dim + ( G ) ≥ N and dim + ( G ) − dim( G ) ≥ N .
---
paper_title: Structure-activity maps for visualizing the graph variables arising in drug design

paper_content:

Structure-activity problems are characterized by the topological and topographical character of the structural information determining the activity. Traditional statistical methodology requires that this predictive information be mapped to a vector space. To circumvent this vexing conversion of structural information to vector form, the edge-deletion metric is defined on the space of chemical graphs that defines the topology of the molecules. This paper proposes structure-activity maps and transformation-effect maps for directly visualizing the structure-activity relationships. The maps are illustrated using the hypotensive activities of clonidine analogs and the sweet taste of Perillartine analogs.
---
paper_title: The partition dimension of a graph

paper_content:

For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is \( d(v, S) = \min \{d(v, x) | x \in S\} \). For an ordered k-partition \( \Pi = \{S_1, S_2, \cdots, S_k\} \)> of V(G), the representation of v with respect to \( \Pi \) is the k-vector \( r(v | \Pi) = (d(v, S_1), \,d(v, S_2), \cdots, \,d(v, S_k)) \). The k-partition \( \Pi \) is a resolving partition if the k-vectors \( r(v | \Pi), \,v \in V(G) \), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. It is shown that the partition dimension of a graph G is bounded above by 1 more than its metric dimension. An upper bound for the partition dimension of a bipartite graph G is given in terms of the cardinalities of its partite sets, and it is shown that the bound is attained if and only if G is a complete bipartite graph. Graphs of order n having partition dimension 2, n, or n— 1 are characterized.
---
paper_title: FIRE: a subroutine for fire-protection network analysis

paper_content:

FIRE is a FORTRAN subroutine designed to compute fire protection sets in facility fire spread networks. The input consists of (a) a network in which the vertices are fire areas and the arcs are fire barriers between physically adjacent areas, (b) a collection of critical combinations of equipment locations called target vertices, and (c) costs for protecting the individual areas from fire and for preventing fire spread through the barriers. FIRE computes a relatively inexpensive subset of areas and barriers, called a fire protection set, which, if protected from fire, will guarantee that no single-source fire can destroy any critical equipment combination. Because it will compute only some of the many possible fire protection sets, FIRE produces solutions that may not have the minimum possible cost.
---
paper_title: Graphs of order n with locating-chromatic number n-1

paper_content:

For a coloring c of a connected graph G, let Π = (C1, C2, ..., Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code cΠ(v) of v is the ordered k-tuple (d(v, C1), d(v, C2),..., d(v, Ck)), where d(v, Ci) = min{d(v, x): x ∈ Ci} for 1 ≤ i ≤ k. If distinct vertices have distinct color codes, then c is called a locating-coloring. The locating-chromatic number χL(G) is the minimum number of colors in a locating-coloring of G. It is shown that if G is a connected graph of order n ≥ 3 containing an induced complete multipartite subgraph of order n - 1, then (n + 1)/2 ≤ χL(G) ≤ n and, furthermore, for each integer k with (n + 1)/2 ≤ k ≤ n, there exists such a graph G of order n with χL(G) = k. Graphs of order n containing an induced complete multipartite subgraph of order n - 1 are used to characterize all connected graphs of order n ≥ 4 with locating-chromatic number n - 1.
---
paper_title: Domination and location in acyclic graphs

paper_content:

Locating-dominating sets are of interest in safeguard applications of graphical models of facilities. A subset S of the vertex set V of a graph G is a dominating set if each vertex u ϵ V - S is adjacent to at least one vertex in S. For each v in V - S let S(v) denote the set of vertices in S which are adjacent to v. A dominating set S is defined to be “locating” if for any two vertices v and w in V - S one has S(v) ≠ S(w). Sharp bounds on the cardinality of locating-dominating sets for arbitrary graphs on p vertices and for trees on p vertices are given, and a linear (that is O(P)) algorithm for finding a minimum cardinality locating-dominating set in an acyclic graph is presented.
---
paper_title: ON RESOLVING EDGE COLORINGS IN GRAPHS

paper_content:

We study the relationships between the resolving edge chromatic number and other graphical parameters and provide bounds for the resolving ::: edge chromatic number of a connected graph.
---
paper_title: Resolvability and the upper dimension of graphs

paper_content:

Abstract For an ordered set W = { w 1 , w 2 ,…, w k } of vertices and a vertex v in a connected graph G , the (metric) representation of v with respect to W is the k -vector r ( v | W ) = ( 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 representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented. A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim( G ). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim + ( G ). The resolving number res( G ) of a connected graph G is the minimum k such that every k -set W of vertices of G is also a resolving set of G . Then 1 ≤ dim( G ) ≤ dim + ( G ) ≤ res( G ) ≤ n − 1 for every nontrivial connected graph G of order n . It is shown that dim + ( G ) = res( G ) = n − 1 if and only if G = K n , while dim + ( G ) = res( G ) = 2 if and only if G is a path of order at least 4 or an odd cycle. The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a , b of integers with 2 ≤ a ≤ b , there exists a connected graph G with dim( G ) = dim + ( G ) = a and res( G ) = b . Also, for every positive integer N , there exists a connected graph G with res( G ) − dim + ( G ) ≥ N and dim + ( G ) − dim( G ) ≥ N .
---
paper_title: The independent resolving number of a graph

paper_content:

For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector \[ c_W(v) = (d(v, w_1), d(v, w_2), \dots , d(v, w_k) ). \] The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathop {\mathrm ir}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm ir}(G) = 1$, $n-1$, $n-2$, and present several realization results. It is shown that for every pair $r, k$ of integers with $k \ge 2$ and $0 \le r \le k$, there exists a connected graph $G$ with $\mathop {\mathrm ir}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
---
paper_title: The independent resolving number of a graph

paper_content:

For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector \[ c_W(v) = (d(v, w_1), d(v, w_2), \dots , d(v, w_k) ). \] The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathop {\mathrm ir}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm ir}(G) = 1$, $n-1$, $n-2$, and present several realization results. It is shown that for every pair $r, k$ of integers with $k \ge 2$ and $0 \le r \le k$, there exists a connected graph $G$ with $\mathop {\mathrm ir}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
---
paper_title: The partition dimension of a graph

paper_content:

For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is \( d(v, S) = \min \{d(v, x) | x \in S\} \). For an ordered k-partition \( \Pi = \{S_1, S_2, \cdots, S_k\} \)> of V(G), the representation of v with respect to \( \Pi \) is the k-vector \( r(v | \Pi) = (d(v, S_1), \,d(v, S_2), \cdots, \,d(v, S_k)) \). The k-partition \( \Pi \) is a resolving partition if the k-vectors \( r(v | \Pi), \,v \in V(G) \), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. It is shown that the partition dimension of a graph G is bounded above by 1 more than its metric dimension. An upper bound for the partition dimension of a bipartite graph G is given in terms of the cardinalities of its partite sets, and it is shown that the bound is attained if and only if G is a complete bipartite graph. Graphs of order n having partition dimension 2, n, or n— 1 are characterized.
---
paper_title: The independent resolving number of a graph

paper_content:

For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector \[ c_W(v) = (d(v, w_1), d(v, w_2), \dots , d(v, w_k) ). \] The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathop {\mathrm ir}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm ir}(G) = 1$, $n-1$, $n-2$, and present several realization results. It is shown that for every pair $r, k$ of integers with $k \ge 2$ and $0 \le r \le k$, there exists a connected graph $G$ with $\mathop {\mathrm ir}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
---
paper_title: Stratification and domination in graphs II

paper_content:

Abstract A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class.) We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v . The F -domination number of a graph G is the minimum number of red vertices of G in a red–blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v . In this paper we investigate the F -domination number when (i) F is a 2-stratified path P 3 on three vertices rooted at a blue vertex which is a vertex of degree 1 in the P 3 and is adjacent to a blue vertex and with the remaining vertex colored red, and (ii) F is a 2-stratified K 3 rooted at a blue vertex and with exactly one red vertex.
---
paper_title: Graphs of order n with locating-chromatic number n-1

paper_content:

For a coloring c of a connected graph G, let Π = (C1, C2, ..., Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code cΠ(v) of v is the ordered k-tuple (d(v, C1), d(v, C2),..., d(v, Ck)), where d(v, Ci) = min{d(v, x): x ∈ Ci} for 1 ≤ i ≤ k. If distinct vertices have distinct color codes, then c is called a locating-coloring. The locating-chromatic number χL(G) is the minimum number of colors in a locating-coloring of G. It is shown that if G is a connected graph of order n ≥ 3 containing an induced complete multipartite subgraph of order n - 1, then (n + 1)/2 ≤ χL(G) ≤ n and, furthermore, for each integer k with (n + 1)/2 ≤ k ≤ n, there exists such a graph G of order n with χL(G) = k. Graphs of order n containing an induced complete multipartite subgraph of order n - 1 are used to characterize all connected graphs of order n ≥ 4 with locating-chromatic number n - 1.
---
paper_title: Graphs of order n with locating-chromatic number n-1

paper_content:

For a coloring c of a connected graph G, let Π = (C1, C2, ..., Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code cΠ(v) of v is the ordered k-tuple (d(v, C1), d(v, C2),..., d(v, Ck)), where d(v, Ci) = min{d(v, x): x ∈ Ci} for 1 ≤ i ≤ k. If distinct vertices have distinct color codes, then c is called a locating-coloring. The locating-chromatic number χL(G) is the minimum number of colors in a locating-coloring of G. It is shown that if G is a connected graph of order n ≥ 3 containing an induced complete multipartite subgraph of order n - 1, then (n + 1)/2 ≤ χL(G) ≤ n and, furthermore, for each integer k with (n + 1)/2 ≤ k ≤ n, there exists such a graph G of order n with χL(G) = k. Graphs of order n containing an induced complete multipartite subgraph of order n - 1 are used to characterize all connected graphs of order n ≥ 4 with locating-chromatic number n - 1.
---
paper_title: The point-arboricity of a graph

paper_content:

The point-arboricity ρ(G) of a graphG is defined as the minimum number of subsets in a partition of the point set ofG so that each subset induces an acyclic subgraph. Dually, the tuleity τ(G) is the maximum number of disjoint, point-induced, non-acyclic subgraphs contained inG. Several results concerning these numbers are presented, among which are formulas for the point arboricity and tulgeity of the class of completen-partite graphs.
---
paper_title: The partition dimension of a graph

paper_content:

For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is \( d(v, S) = \min \{d(v, x) | x \in S\} \). For an ordered k-partition \( \Pi = \{S_1, S_2, \cdots, S_k\} \)> of V(G), the representation of v with respect to \( \Pi \) is the k-vector \( r(v | \Pi) = (d(v, S_1), \,d(v, S_2), \cdots, \,d(v, S_k)) \). The k-partition \( \Pi \) is a resolving partition if the k-vectors \( r(v | \Pi), \,v \in V(G) \), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. It is shown that the partition dimension of a graph G is bounded above by 1 more than its metric dimension. An upper bound for the partition dimension of a bipartite graph G is given in terms of the cardinalities of its partite sets, and it is shown that the bound is attained if and only if G is a complete bipartite graph. Graphs of order n having partition dimension 2, n, or n— 1 are characterized.
---
paper_title: The Decomposition Dimension of Graphs

paper_content:

For an ordered k-decomposition ? = {G1, G2,…,G k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G1), d(e, G2),…,d(e, G k )), where d(e, G i ) is the distance from e to G i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K n ) ≤⌊(2n + 5)/3⌋ for n≥ 3.
---
paper_title: On the decomposition dimension of trees

paper_content:

Abstract A decomposition F = {F 1 ,F 2 ,…,F r } of the edge set of a graph G is called a resolving r -decomposition if for any pair of edges e 1 and e 2 , there exists an index i such that d ( e 1 , F i )≠ d ( e 2 , F i ), where d ( e , F ) denotes the distance from e to F . The decomposition dimension dec( G ) of a graph G is the least integer r such that there exists a resolving r -decomposition. It is proved that for any k ⩾3 and r⩾⌈ log 2 k⌉+1 , there exists a tree T such that the maximum degree of T is k and dec( T ) is r . The relation between the decomposition dimension and the diameter of a tree is also discussed.
---
paper_title: The Decomposition Dimension of Graphs

paper_content:

For an ordered k-decomposition ? = {G1, G2,…,G k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G1), d(e, G2),…,d(e, G k )), where d(e, G i ) is the distance from e to G i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K n ) ≤⌊(2n + 5)/3⌋ for n≥ 3.
---
paper_title: On the decomposition dimension of trees

paper_content:

Abstract A decomposition F = {F 1 ,F 2 ,…,F r } of the edge set of a graph G is called a resolving r -decomposition if for any pair of edges e 1 and e 2 , there exists an index i such that d ( e 1 , F i )≠ d ( e 2 , F i ), where d ( e , F ) denotes the distance from e to F . The decomposition dimension dec( G ) of a graph G is the least integer r such that there exists a resolving r -decomposition. It is proved that for any k ⩾3 and r⩾⌈ log 2 k⌉+1 , there exists a tree T such that the maximum degree of T is k and dec( T ) is r . The relation between the decomposition dimension and the diameter of a tree is also discussed.
---
paper_title: ON RESOLVING EDGE COLORINGS IN GRAPHS

paper_content:

We study the relationships between the resolving edge chromatic number and other graphical parameters and provide bounds for the resolving ::: edge chromatic number of a connected graph.
---

Title: Conditional Resolvability in Graphs: A Survey

Section 1: Introduction
Description 1: Provide an introduction to the topic, including background information, definitions, notation, historical context, and applications of resolving sets in graph theory.

Section 2: Conditional resolving sets
Description 2: Discuss the formation of various resolving parameters by combining the resolving property with other graph-theoretic properties, such as connected, independent, or acyclic sets.

Section 3: Connected resolving sets
Description 3: Examine resolving sets in which the subgraph induced by the set is connected, including the minimum cardinality and properties of connected resolving sets.

Section 4: Independent resolving sets
Description 4: Analyze independent resolving sets within graphs, including conditions for their existence and minimum cardinality.

Section 5: Conditional resolving partitions
Description 5: Explore the partitioning of vertex sets into classes based on certain conditions, and the concept of resolving partitions and partition dimensions.

Section 6: Independent resolving partitions
Description 6: Investigate partitions that are both independent and resolving, introducing resolving-colorings and their related parameters.

Section 7: Acyclic resolving partitions
Description 7: Consider partitions where each subset induces an acyclic subgraph and discuss the acyclic partition dimension.

Section 8: Conditional resolving decompositions
Description 8: Delve into the decomposition of graphs into subgraphs that meet certain conditions, focusing on resolving decompositions and their minimum dimensions.

Section 9: Connected resolving decompositions
Description 9: Examine resolving decompositions where each subgraph is connected, including definitions, properties, and bounds.

Section 10: Independent resolving decompositions
Description 10: Discuss independent resolving decompositions from an edge-coloring perspective and introduce the concept of resolving edge chromatic numbers.