PII. S0161171204311403 http://ijmms.hindawi.com
© Hindawi Publishing Corp.
CONDITIONAL RESOLVABILITY IN GRAPHS: A SURVEY
VARAPORN SAENPHOLPHAT and PING ZHANG Received 29 November 2003
For an ordered setW= {w1, w2, . . . , wk}of vertices and a vertexvin a connected graphG, the code ofvwith respect toWis thek-vectorcW(v)=(d(v, w1), d(v, w2), . . . , d(v, wk)), where d(x, y)represents the distance between the verticesxandy. The setWis a resolving set for Gif distinct vertices ofGhave distinct codes with respect toW. The minimum cardinality of a resolving set forGis 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.
2000 Mathematics Subject Classification: 05C12, 05C20, 05C90.
1. Introduction. We refer to [13] for graphical theoretical notation and terminology not described in this paper. Thedistanced(u, v)between two verticesuand v in a connected graph G is the length of a shortestu−v path inG. For an ordered set W= {w1, w2, . . . , wk} ⊆V (G)and a vertexvofG, thek-vector
cW(v)= d
v, w1
, d v, w2
, . . . , d v, wk
(1.1)
is thecodeofv with respect toW. The setW is called aresolving set forGif distinct vertices have distinct codes with respect toW. A resolving set containing a minimum number of vertices is aminimum resolving setor abasisforG. The (metric)dimension dim(G)is the number of vertices in a basis forG.
For example, consider the graphGshown inFigure 1.1. The ordered setW1= {v1, v3} is not a resolving set for Gsince cW1(v2)=(1,1)=cW1(v4), that is, Gcontains two vertices with the same code. On the other hand,W2= {v1, v2, v3}is a resolving set for Gsince the codes for the vertices ofGwith respect toW2are
cW2
v1
=(0,1,1), cW2
v2
=(1,0,1), cW2
v3
=(1,1,0), cW2
v4
=(1,2,1), cW2
v5
=(2,1,1), (1.2)
which are distinct. However,W2is not a minimum resolving set forGsinceW3= {v1, v2} is also a resolving set. The codes for the vertices ofGwith respect toW3are
cW3
v1
=(0,1), cW3
v2
=(1,0), cW3
v3
=(1,1), cW3
v4
=(1,2), cW3
v5
=(2,1). (1.3)
G:
v1 v2
v3
v4 v5
Figure1.1. Illustrating resolving sets.
Since no single vertex constitutes a resolving set forG, it follows thatW3is a minimum resolving set or a basis for this graphG, and so dim(G)=2.
The example just presented also illustrates an important point. When determining whether a given setWof vertices of a graphGis a resolving set forG, we only need to investigate the vertices ofV (G)−Wsincew∈Wis the only vertex ofGwhose distance fromwis 0.
As described in [22], the idea of a resolving set (and of a minimum resolving set) has appeared in the literature previously. In [50], and later in [52], Slater introduced this concept and usedlocating setfor what we have called resolving set. He referred to the cardinality of a minimum resolving set in a graphGas itslocation numberloc(G).
Slater described the usefulness of these ideas when working with U.S. sonar and Coast Guard Loran (Long range aids to navigation) stations. Independently, Harary and Melter [28] discovered the concept of a location number as well, but used the term metric di- mension, rather than location number, the terminology that we have adopted. Recently, these concepts were rediscovered by Johnson [32,33] of the Pharmacia Company while attempting to develop a capability of large datasets of chemical graphs. More applica- tions of this concept to navigation of robots in networks and other areas are discussed in [4,29,30,31,34]. It was noted in [27, page 204] that determining the locating num- ber of a graph is an NP-complete problem. Resolving sets in graphs have been studied further in [1,2,3,5,6,8,14,20,21,24,34,37,38]. Recently, these concepts have been extended in various ways and studied for different subjects in graph theory, includ- ing such diverse aspects as the partition of the vertex set, decomposition, orientation, domination, coloring in graphs [15,16,17,19,23, 25,35,36,39,47,51], and others [22]. Many invariants arising from the study of resolving sets in graph theory offer sub- jects for applicable research. 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.
2. Conditional resolving sets. Many resolving parameters are formed by combin- ing resolving property with another common graph-theoretic property such as being connected, independent, or acyclic. The generic nature of conditional resolvability in graphs provides various ways of defining new resolving parameters by considering dif- ferent conditions.
2.1. Connected resolving sets. In general, a connected graphGcan have many re- solving sets. In this section, we study those resolving sets whose vertices are located
“close” to one another. A resolving setWofGisconnectedif the subgraphWinduced byWis a connected subgraph ofG. The minimum cardinality of a connected resolving
set W in a graph G is theconnected resolving number cr(G). A connected resolving set of cardinality cr(G)is called a cr-setofG. This concept was introduced in [43] and further studied in [42, 45,46]. Since the vertex setV (G)ofG is a resolving set and V (G) =Gis connected, cr(G) is defined for every connected graphG. Since every connected resolving set is a resolving set, dim(G)≤cr(G)for all connected graphsG.
Furthermore, dim(G)=cr(G)if and only ifGcontains a connected basis.
The relationship between cr-sets and bases in a nontrivial connected graphGhas been studied in [45]. IfWandWare two sets of vertices of a graphGsuch thatWis a resolving set ofGandW⊆W, thenWis also a resolving set ofG. Therefore, ifWis a basis ofGsuch thatWis disconnected, then surely there is a smallest supersetWof Wfor whichWis connected. This suggests the following question: for each basisW of a nontrivial connected graphG, does there exist a cr-setWofGsuch thatW⊆W? In [45], it was shown that this question has a negative answer.
Proposition2.1. There is an infinite class of connected graphsG such that some cr-sets ofGcontain a basis ofGand others contain no basis ofG.
Proposition 2.1suggests yet another question. For each connected graphG, do there existsomecr-setWand some basis W ofGwithW ⊆W? It was shown in [45] that even this question has a negative answer as well, by presenting a stronger result. LetX andY be two sets of vertices in a connected graphG. ThedistancebetweenXandY is defined as
d(X, Y )=min
d(x, y)|x∈Xandy∈Y
. (2.1)
Theorem 2.2. For each positive integerN, there is an infinite class of connected graphsGsuch thatd(W , S)≥Nfor every basisWofGand everycr-setS ofG.
The following three results give relationships between cr-sets and bases in some well- known classes of graphs, namely, complete graphs, complete bipartite graphs, cycles, and trees.
Proposition2.3. IfGis a complete graph of order at least3or a complete bipartite graph that is not a star, then a setWof vertices ofGis a basis ofGif and only ifWis a cr-set ofG.
Proposition2.4. For a cycleCnof ordern≥4, everycr-set ofCnis a basis ofCn. The converse ofProposition 2.4is not true forn≥5 since some basis ofCnconsists of two nonadjacent vertices ofCnand, therefore, it is not a cr-set ofCn.
Proposition2.5. IfT is a tree that is not a path, then everycr-set ofT contains a basis ofT as a proper subset.
IfGis a connected graph of ordern, then every set ofn−1 vertices ofGis a resolving set ofG. Moreover, every nontrivial connected graphGcontains a vertexvthat is not a cut-vertex, and soV (G)−{v}is a connected resolving set forG. Thus
1≤cr(G)≤n−1 (2.2)
for all connected graphs Gof order n≥3. The lower and upper bounds in (2.2) are both sharp. In fact, all connected graphsG of ordern≥2 with cr(G)=1, n−1 are characterized in [43].
Theorem2.6. LetGbe a connected graph of ordern≥2. Then (a) cr(G)=1if and only ifG=Pn,
(b) cr(G)=n−1if and only ifG=KnorG=K1,n−1.
Moreover, for each pairk, nwith1≤k≤n−1, there is a connected graph of ordern with connected resolving numberk.
IfG is a connected graph with dim(G)=a and cr(G)=b, then 1≤a≤b. On the other hand, all pairs a, b of positive integers with a≤b that can be realizable as the dimension and connected resolving number of some connected graph have been determined in [43].
Theorem2.7. For positive integersa,bwitha≤b, there exists a connected graph Gwithdim(G)=aandcr(G)=bif and only if(a, b)∉{(1, k):k≥2}.
All triplesa,b,nof positive integers that can be realized as the dimension, connected resolving number, and order, respectively, of some connected graph have also been determined in [43].
Theorem2.8. Leta,b,nbe integers withn≥5. Then there exists a connected graph Gof ordernsuch thatdim(G)=aandcr(G)=bif and only ifa,b,nsatisfy one of the following:
(a) a=b=1,
(b) b=n−1anda∈ {n−2, n−1}, (c) 2≤a≤b≤n−2.
In general, the graphs we have seen have had several cr-sets. It was shown in [46]
that for every integerk≥2, there exists a graph with a unique cr-set of cardinalityk.
Furthermore, this result can be extended to the following.
Theorem2.9. For every pairr,kof integers withk≥2and0≤r≤k, there exists a connected graphGsuch thatcr(G)=kand exactlyrvertices ofGbelong to everycr-set ofG.
A resolving setWof a nontrivial connectedGis aminimal resolving setif no proper subset of W is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim+(G). A minimal resolving set of cardinality dim+(G) is an upper basis forG. Since every minimum resolving set is a minimal resolving set forG, it follows that dim(G)≤dim+(G). These concepts were introduced and studied in [14]. Similarly, a connected resolving set W ofG is aminimal connected resolving set if no proper subset ofW is a connected resolving set. The maximum cardinality of a minimal connected resolving set is theupper connected resolving number cr+(G).
These concepts were introduced in [43] and further studied in [42,46]. Certainly, ifG is a nontrivial connected graph of ordern, then
1≤cr(G)≤cr+(G)≤n−1. (2.3)
It was shown in [46] that there is no “intermediate value theorem” for minimal con- nected resolving sets, that is, ifkis an integer such that cr(G) < k <cr+(G), then there need not exist a minimal connected resolving set of cardinalitykinG.
In order to present the connected resolving numbers and upper connected resolving numbers of some well-known classes of graphs, we need some additional definitions and notation. A vertex of degree at least 3 in a graphGwill be called amajor vertex.
An endvertexuofGis said to be aterminal vertex of a major vertexvofGifd(u, v) <
d(u, w)for every other major vertexwofG. Theterminal degreeter(v)of a major vertexvis the number of terminal vertices ofv. A major vertexv ofGis anexterior major vertex ofGif it has positive terminal degree. Letσ (G)denote the sum of the terminal degrees of the major vertices ofGand let ex(G)denote the number of exterior major vertices ofG. In fact,σ (G)is the number of endvertices ofG.
(a) IfG=Knforn≥3 orG=K1,n−1forn≥4, then cr+(G)=cr(G)=n−1.
(b) IfG=Pnforn≥2, then cr+(G)=cr(G)=1.
(c) IfG=Cnforn≥4, then cr+(G)=cr(G)=2.
(d) Fork≥2, letG=Kn1,n2,...,nk be a completek-partite graph that is not a star. Let n=n1+n2+···+nkand letbe the number of 1’s in{ni: 1≤i≤k}. Then
cr+(G)=cr(G)=
n−k if=0,
n−k+−1 if≥1. (2.4)
(e) LetTbe a tree that is not a path, having ordern≥4 andpexterior major vertices v1, v2, . . . , vp. For 1≤i≤p, letui1, ui2, . . . , uiki be the terminal vertices ofviand letij=d(vi, uij) (1≤j≤ki). Then
cr+(T )=cr(T )=n+σ (T )−ex(T )−
i,j
ij. (2.5)
We have seen inTheorem 2.6thatKnandK1,n−1are the only connected graphs of ordern≥4 with connected resolving numbern−1. In fact, this is also true for the upper connected numbers of graphs [46].
Theorem2.10. LetGbe a connected graph of ordern≥4. Thencr+(G)=n−1if and only ifG=KnorG=K1,n−1.
Note that every graphGencountered thus far has the property that either cr+(G)= cr(G)or cr+(G)−cr(G)≤2. This might lead one to believe that cr+(G)and cr(G)are close for every connected graphG. However, this is not the case. In fact, every paira, bof integers with 2≤a≤bis realizable as the connected resolving number and upper connected resolving number of some graph, as shown in [42].
Theorem2.11. Letaandbbe integers with1≤a≤b. Then there exists a connected graphGwithcr(G)=aandcr+(G)=bif and only if(a, b)≠(1, i)for alli≥2.
2.2. Independent resolving sets. Independent sets of vertices in graphs form one of the most commonly studied concepts in graph theory. The independent sets of max- imum cardinality are calledmaximum independent setsand these are the independent
sets that have received the most attention. The number of vertices in a maximum inde- pendent set in a graphGis theindependence number(orvertex independence number) ofGand is denoted byβ(G). Some graphsGcontain (ordered) independent setsWsuch that the vertices ofG are uniquely distinguished by their distances from the vertices ofW. In [18], we study the existence of such independent sets in graphs and, when they exist, investigate the minimum cardinality of such a set.
Anindependent resolving set W in a connected graphGis both resolving and inde- pendent. The cardinality of a minimum independent resolving set (or simply an ir-set) in a graphGis theindependent resolving number ir(G). This concept was introduced and studied in [18]. LetGbe a connected graph of orderncontaining an independent resolving set. Since every independent resolving set ofGis a resolving set, it follows that
1≤dim(G)≤ir(G)≤β(G)≤n−1. (2.6) A lower bound for ir(G)of a connected graphGin terms of its maximum degree∆(G) was given in [18].
Proposition2.12. IfGis a nontrivial connected graph for whichir(G)is defined, then
ir(G)≥ log3
∆(G)+1
. (2.7)
Furthermore, this bound is sharp.
Not all graphs have an independent resolving set, however, and so ir(G)is not de- fined for all graphsG. In order to present the results on the existence of independent resolving sets in graphs, we need some additional definitions. Two verticesuandvin a connected graphGaredistance-similarifd(u, x)=d(v, x)for allx∈V (G)−{u, v}. For a vertex v in a graph G, let N(v) be the set of vertices adjacent to v and let N[v]=N(v)∪{v}. Then two verticesuandvin a connected graph are distance-similar if and only if(1) uv∉E(G)and N(u)=N(v) or(2) uv∈E(G)and N[u]=N[v].
Distance similarity in a graphGis an equivalence relation onV (G). The following ob- servations are useful.
Observation2.13. IfUis a distance-similar equivalence class in a connected graph Gwith|U| =p≥2, then every resolving set ofGcontains at leastp−1 vertices fromU.
Thus, ifGhaskdistance-similar equivalence classes and ir(G)is defined, then
n−k≤dim(G)≤ir(G). (2.8)
Observation 2.14. Let G be a connected graph and let U be a distance-similar equivalence class inG with |U| ≥3. IfU is not independent inG, then ir(G) is not defined.
The converse ofObservation 2.14is not true. For example, letG=K3,3with partite setsV1and V2. Then ir(G)is not defined. On the other hand,V1andV2are the only
distance-similar equivalence classes and they are both independent. The following re- sult appears in [18].
Proposition 2.15. LetG be a connected graph of order n≥6for whichir(G) is defined. IfWis an independent resolving set ofG, thendegw≤n−3for everyw∈W.
The following corollary is a consequence ofProposition 2.15.
Corollary2.16. LetGbe a connected graph of ordern≥6.
(a) IfGcontains two nonadjacent vertices of degreen−2, thenir(G)is not defined.
(b) IfGcontains two vertices of degreen−1, thenir(G)is not defined.
On the other hand, there exist graphsGof ordern≥6 having two adjacent vertices of degreen−2 for which ir(G)is defined. For example, letG be the graph obtained fromKn−2, whereV (Kn−2)= {v1, v2, . . . , vn−2}, andP2:x, y by adding the edgesxvi
(1≤i≤n−3) and yvj (2≤j ≤ n−2). Then W = {v1, v2, . . . , vn−4} is a minimum independent resolving set ofG, and so ir(G)=n−4.
Proposition2.17. LetGbe a connected graph of ordern≥4. Suppose thatGcon- tains two distinct distance-similar equivalence classesU1andU2of cardinality at least2.
If some vertex ofU1is adjacent to a vertex ofU2, thenir(G)is not defined.
The converse ofProposition 2.17 is not true. For example, letG be the graph ob- tained from two copies of K4, whose vertex sets areU1= {u1, u2, u3, u4}and V1= {v1, v2, v3, v4}, by adding the edgeu4v4. ThenU1−{u4}andV1−{v4}are two distinct distance-similar equivalence classes of G. ByObservation 2.14, ir(G) does not exist.
However, no edge joins a vertex inU1−{u4}and a vertex inV1−{v4}.
The existence of independent resolving sets in some well-known classes of graphs is determined in [18]. IfGis a nontrivial connected graph of ordernfor which ir(G) exists, then 1≤ir(G)≤n−1. The following result characterizes all nontrivial connected graphsGof ordernfor which ir(G)∈ {1, n−2, n−1}.
Theorem2.18. LetGbe a connected graph of ordern≥2for whichir(G) exists.
Then
(a) ir(G)=1if and only ifG=Pn,
(b) ir(G)=n−2if and only ifn≥3andG=K1,n−1orn=4andG=(K2∪K1)+K1, (c) ir(G)=n−1if and only ifn=2andG=K2.
All pairsk,nof positive integers withk≤nthat are realizable as the independent resolving number and the order of some connected graph are also determined in [18].
Theorem 2.19. For each pairk, n of positive integers withk≤n, there exists a connected graphGof ordernwithir(G)=kif and only if(k, n)=(1,2)or1≤k≤n−2.
It was also shown in [18] that certain pairsa,bare realizable as the dimension and the independent resolving number of some connected graph.
Theorem2.20. For every paira,bof integers with2≤a≤b≤ 3a/2, there exists a connected graphGsuch thatdim(G)=aandir(G)=b.
By Theorem 2.20, every paira, b of positive integers with 2≤a≤b≤ 3a/2 is realizable as the dimension and the independent resolving number of some connected graph. Furthermore, for each pair a,b of positive integers with 4≤a≤b, it can be shown that (1) there exists a connected graphF with dim(F )=ir(F )=aandβ(F )=b, (2) there exists a connected graphGwith dim(G)=aandβ(G)=bsuch that dim(G)≠ ir(G), (3) there exists a connected graph H with ir(H)=a and β(H)=b such that dim(H)≠ir(H). However, we do not have a complete solution to the following problem.
Problem2.21. For which triplesa,b,cof positive integers with 2≤a≤b≤cdoes there exist a connected graphGsuch that dim(G)=a, ir(G)=b, andβ(G)=c?
3. Conditional resolving partitions. As described in [9,10], dividing the vertex set of a graph into classes according to some prescribed rule is a fundamental process in graph theory. For example, the vertices of a graph can be divided into cut-vertices and non-cut-vertices. Equivalently, the vertices of a tree are divided into its leaves and nonleaves. The vertices of a graph can also be partitioned according to the degrees of its vertices. When studying distance, the vertices of a connected graph are partitioned according to their distance from the root. Perhaps the best known example of this process, however, is graph coloring, where the vertex set of a graph is partitioned into classes each of which is independent in the graph. In [19], the vertices of a connected graphGare represented by other means, namely, through partitions ofV (G)and the distances between each vertex ofGand the subsets in the partition.
For a setSof vertices of a connected graphGand a vertexvofG, thedistanced(v, S) betweenvandS is defined as
d(v, S)=min
d(v, x):x∈S
. (3.1)
For an orderedk-partitionΠ= {S1, S2, . . . , Sk}ofV (G)and a vertexvofG, thecode of vwith respect toΠis defined as thek-vector
cΠ(v)= d
v, S1
, d v, S2
, . . . , d v, Sk
. (3.2)
The partitionΠ is calleda resolving partitionforG if the distinct vertices ofGhave distinct codes with respect to Π. The minimum k for which there is a resolving k- partition ofV (G)is thepartition dimensionpd(G)ofG.
As an illustration of these concepts, consider the graphGinFigure 3.1.
LetΠ1= {S1, S2, S3, S4}, whereS1= {v1, v2},S2= {v3},S3= {v4}, andS4= {v5}. Then the five codes with respect toΠ1are
cΠ1 v1
=(0,1,1,1), cΠ1 v2
=(0,1,2,2), cΠ1 v3
=(1,0,1,2), cΠ1
v4
=(1,1,0,1), cΠ1 v5
=(1,2,1,0). (3.3)
G: v5 v2 v1
v4 v3
Figure3.1. Illustrating resolving partitions.
Since the five codes are distinct,Π1is a resolving partition ofG. However,Π1is not a minimum resolving partition ofG. To see this, letΠ2= {S1, S2, S3}, whereS1= {v1, v2}, S2= {v3}, andS3= {v4, v5}. Then the corresponding codes are
cΠ2 v1
=(0,1,1), cΠ2 v2
=(0,1,2), cΠ2 v3
=(1,0,1), cΠ2
v4
=(1,1,0), cΠ2 v5
=(1,2,0). (3.4)
So,Π2is a resolving partition ofG. Moreover, since no 2-partition is a resolving partition ofG, it follows thatΠ2is a minimum resolving partition ofG, and so pd(G)=3. The resolving partition and partition dimension of a graph were introduced and studied in [19,23].
3.1. Connected resolving partitions. For a connected graphG, a resolving partition Π= {S1, S2, . . . , Sk}ofV (G)is defined to beconnectedin [41] if the subgraphSiinduced by each subsetSi(1≤i≤k) is connected inG. The minimumkfor which there is a connected resolvingk-partition ofV (G)is theconnected partition dimensioncpd(G) of G. A connected resolving partition ofV (G) containing cpd(G)elements is called aminimum connected resolving partition(or cr-partition) ofV (G). IfGis a nontrivial connected graph withV (G)= {v1, v2, . . . , vn}, then then-partition{S1, S2, . . . , Sn}, where Si= {vi}for 1≤i≤n, is a connected resolving partition forG. Thus, cpd(G)is defined for every nontrivial connected graphG. Certainly, every connected resolving partition of a connected graph is a resolving partition. Thus, ifGis a connected graph of order n≥2, then
2≤pd(G)≤cpd(G)≤n. (3.5)
Moreover, pd(G)=cpd(G)if and only ifGcontains a minimum resolving partition that is connected.
LetΠbe a partition ofV (G). A partitionΠofV (G)is called arefinement ofΠif each element ofΠis a subset of some element ofΠ. It was shown in [41] that every refinement of a resolving partition of a connected graphGis also a resolving partition ofG. If we are given a minimum resolving partitionΠof a connected graphG, then we can find a connected resolving partitionΠofG, whereΠis a refinement ofΠ. Indeed, the partition each of whose elements consists of a single vertex has this property.
However,Πneed not be a minimum connected resolving partition for G. In fact, it
may be the case that no minimum connected resolving partition is a refinement of any minimum resolving partition ofV (G).
Upper and lower bounds for the connected partition dimension of a connected graph in terms of its order and diameter were established in [41]. For integersnanddwith 1≤d < n, we defineg(n, d)as the least positive integerkfor whichkdk−1≥n. Thus g(n,1)=nfor alln≥2.
Theorem3.1. IfGis a connected graph of ordern≥3and diameterd, then g(n, d)≤pd(G)≤cpd(G)≤n−d+1. (3.6) It was shown in [19] that for each integern≥2, the pathPn of ordernis the only connected graph of ordernhaving partition dimension 2, the complete graphKnis the only connected graph of ordernhaving partition dimensionn, and the graphsK1,n−1, Kn−e,K1+(K1∪Kn−2)are the only connected graphs of ordern≥3 with partition dimensionn−1. Those graphs are also the only connected graphs of ordern≥3 with connected partition dimension 2,n, orn−1, respectively (see [41]).
Theorem3.2. LetGbe a connected graph of ordern≥3. Then (a) cpd(G)=2if and only ifG=Pn,
(b) cpd(G)=nif and only ifG=Kn,
(c) cpd(G)=n−1if and only ifG∈ {K1,n−1, Kn−e, K1+(K1∪Kn−2)}.
We have seen that ifGis a nontrivial connected graph with pd(G)=aand cpd(G)=b, then 2≤a≤b. Furthermore, the nontrivial paths are the only nontrivial connected graphs with partition dimension 2 and connected partition dimension 2. Thus, pd(G)= 2 if and only if cpd(G)=2 if and only ifG=Pn. On the other hand, it was shown in [41] that every paira, b of integers with 3≤a≤b is realizable as the partition dimension and the connected partition dimension, respectively, of some connected graph, as stated next.
Theorem3.3. For every paira,b of integers with3≤a≤b, there is a connected graphGwithpd(G)=aandcpd(G)=b.
The partition dimensions of some special types of trees that are not paths were studied in [23]. There is no general formula, however, for the partition dimension of a tree that is not a path. On the other hand, a formula for the connected partition dimension of a tree that is not a path was established in [41]. Recall thatσ (G)denotes the sum of the terminal degrees of the major vertices of a graphGand ex(G)denotes the number of exterior major vertices ofG, as defined inSection 2.1.
Theorem3.4. IfT is a tree that is not a path, then
cpd(T )=σ (T )−ex(T )+1. (3.7) 3.2. Independent resolving partitions. For a connected graphG, ak-partitionΠ= {S1, S2, . . . , Sk}isindependent if the subgraphSiinduced bySiis independent in G for each i (1≤i≤k). Partitions of V (G)that are both resolving and independent were studied in [5, 6] and calledresolving-colorings (orlocating-colorings) since the
coloring ofGobtained by coloring each vertex ofSi(1≤i≤k)the coloriis a proper coloring. Theresolving-chromatic number (orlocating-chromatic number)χr(G)ofG is the minimumkfor which there is a resolving, independent k-partition ofV (G). It was observed in [5] that for every connected graphG,
χ(G)≤χr(G)≤χ(G)+dim(G), (3.8)
whereχ(G)is the chromatic number ofG. The following result appears in [5].
Theorem3.5. For every connected graphGof ordern≥3,
3≤χr(G)≤n. (3.9)
Moreover,χr(G)=nif and only ifGis a complete multipartite graph.
It was shown in [6] that if G is a connected graph of ordern≥3 containing an induced complete multipartite subgraph of ordern−1, then(n+1)/2≤χr(G)≤nand, furthermore, for each integerkwith(n+1)/2≤k≤n, there exists such a graphGof ordernwithχr(G)=k. Graphs of orderncontaining an induced complete multipartite subgraph of ordern−1 are used to characterize all connected graphs of ordern≥4 with resolving-chromatic numbern−1.
Bounds for the resolving-chromatic number of a graph were established in [5] in terms of its order and diameter.
Theorem3.6. IfGis a connected graph of ordern≥3and diameterd≥2, then
logd+1n≤χr(G)≤n−d+2. (3.10) Theorem3.7. IfGis a connected graph of ordern≥3, diameterd≥2, andχr(G)=k, thenn≤kdk−1−1.
We have seen that ifGis a nontrivial connected graph withχ(G)=aandχr(G)=b, then 2≤a≤b. It was shown in [5] that every paira,b of integers with 2≤a≤b is realizable as the chromatic number and resolving-chromatic number, respectively, of some connected graph.
Theorem3.8. For each paira,bof integers with2≤a≤b, there exists a connected graphGwithχ(G)=aandχr(G)=b.
In [5], the resolving-chromatic numbers of some well-known classes of graphs are determined. Furthermore, the resolving-chromatic number of a tree has been studied.
Theorem3.9. Letn≥5. There exists a tree of ordernhaving resolving-chromatic numberkif and only ifk∈ {3,4, . . . , n−2, n}.
Theorem3.10. Letk≥3. IfTis a tree for which∆(T ) > (k−1)2k−2, thenχr(T ) > k.
Theorem3.11. Let᐀be the class of all trees for which∆(T )=4andχr(T )=3. Then
᐀is infinite. Furthermore, ifT∈᐀, thenT contains a unique vertex of degree4.
3.3. Acyclic resolving partitions. A graph G is acyclic if G has no cycles. Every independent setS of vertices in a graph Ghas the property thatSis acyclic, and many results concerning the chromatic number ofGhave been extended to partitions ofV (G)in which each subset induces an acyclic subgraph. It is natural, therefore, to study resolving partitions in which each subset induces an acyclic subgraph. For a connected graphG, ak-partitionΠ= {S1, S2, . . . , Sk}ofV (G)isacyclic if the subgraph Siinduced bySi is acyclic inGfor eachi(1≤i≤k). Thevertex-arboricity a(G)of Gis defined in [11,12] as the minimumksuch thatV (G)has an acyclick-partition. If an acyclic partitionΠofV (G)is also a resolving partition, thenΠis called aresolving acyclic partitionofG, which was introduced and studied in [48,49]. The minimumk for whichGcontains a resolving acyclick-partition is theacyclic partition dimension apd(G)ofG. Since every resolving acyclic partition is an acyclic partition,
a(G)≤apd(G) (3.11)
for each connected graphG. Furthermore, for every connected graphGof ordern≥2, 2≤pd(G)≤apd(G)≤χr(G)≤n. (3.12) In particular, ifGis a tree, then pd(G)=apd(G). All connected graphs of ordern≥2 with acyclic partition dimension 2,n−1, ornare determined in [49].
Theorem3.12. LetGbe a connected graph of ordern≥2. Then (a) apd(G)=2if and only ifG=Pn,
(b) apd(G)=nif and only ifG=Kn, (c) forn≥5,apd(G)=n−1if and only if
G∈
C4+K1, K1,n−1, Kn−e, K1+
K1∪Kn−2
. (3.13)
Relationships between the acyclic partition dimensions of a connected graph and other graphical parameters, including arboricity, partition dimension, dimension, and resolving-chromatic number, are studied in [48]. The next two results present bounds for the acyclic partition dimension of a connected graph in terms of (1) its resolving- chromatic number, (2) its partition dimension and arboricity, (3) its dimension and arboricity (see [48]).
Theorem3.13. For every nontrivial connected graphG, χr(G)
2 ≤apd(G)≤χr(G). (3.14)
Moreover, for every pair a, b of integers witha≥2andb/2< a≤b, there exists a connected graphGwithapd(G)=aandχr(G)=b.
However, it is not known whether there exists a connected graphGsuch thatχr(G)= 2 apd(G).
Theorem3.14. For every nontrivial connected graphG,
apd(G)≤a(G)pd(G), apd(G)≤a(G)+dim(G). (3.15)
However, just how good the upper bounds inTheorem 3.14are is not known. The girthof a graph (with cycles) is the length of its shortest cycle. Bounds for the acyclic partition dimension of a connected graph in terms of its order and girth were estab- lished in [48].
Theorem3.15. IfGis a connected graph of ordern≥3and girth≥3, then
3≤apd(G)≤n−+3. (3.16)
Furthermore, ifGis a cycle of ordern≥3, thenapd(G)=3. On the other hand,apd(G)= n−+3if and only ifG=KnorG=Cn.
We have seen that if G is a connected graph of order n≥ 2, then 2≤ pd(G) ≤ apd(G)≤χr(G)≤n. It was shown in [5,19] that pd(Kn)=χr(Kn)=nand pd(Pn)= χr(Pn)=2. Moreover, forn≥3, pd(Cn)=3, whileχr(Cn)=3 ifnis odd andχr(Cn)=4 ifnis even. From Theorems3.12and3.15, we then have the following (see [48]).
Corollary3.16. IfG=Kn, Pnforn≥2orG=Cnfor each odd integern≥3, then
pd(G)=apd(G)=χr(G). (3.17)
It is not known whetherCorollary 3.16is also true for other graphs.
Theclique numberof a graph is the maximum order among the complete subgraphs of the graph. A lower bound for the acyclic partition dimension of a connected graph in terms of its clique number is given in [48].
Theorem3.17. For a connected graphGwith the clique numberω, apd(G)≥
ω 2
+1. (3.18)
Moreover, for each integer ω≥2, there exists a connected graph Gω having clique numberωsuch thatapd(Gω)= ω/2+1.
IfGis a nontrivial connected graph of ordernand diameterd, then
2≤apd(G)≤n−d+1. (3.19)
Furthermore, it was shown in [48] that for each tripled,k,nof integers with 2≤d≤ n−2 and 3≤(n−d+1)/2≤k≤n−d+1, there exists a connected graph of order nhaving diameterdand acyclic partition dimensionk. On the other hand, for those triplesd,k,nof integers with 2≤d≤n−2 and 3≤k≤(n−d−1)/2, the following question is open.
Problem3.18. For which triplesd,k,nof integers with 2≤d≤n−2 and 3≤k≤ (n−d−1)/2 does there exist a connected graph of ordern having diameterd and acyclic partition dimensionk?
We have seen that ifG is a connected graph witha(G)=a and apd(G)=b, then 1≤a≤bandb≥2. Next, we study those pairsa,bof integers with 1≤a≤bandb≥2 that are realizable as the vertex-arboricity and acyclic partition dimension of some con- nected graph. Since trees are the only connected graphs having the vertex-arboricity 1, it follows that
a(T )≠apd(T ) (3.20)
for all treesT. Thus we may assume thata≥2. It is known that ifG is a connected graph of ordern, thena(G)≤ n/2. Thus, if apd(G) >n/2, thena(G)≠apd(G). It is known that each paira,bof integers with 2≤a≤b−1 is realizable as the vertex- arboricity and acyclic partition dimension of some connected graph.
Theorem 3.19. For each pair a, b of integers with 2≤a≤b−1, there exists a connected graphGwitha(G)=aandapd(G)=b.
However, it is not known whether there exists a connected graph G with a(G)= apd(G).
IfHis an induced subgraph of a graphG, thena(H)≤a(G). Thus
0<a(H)
a(G) ≤1 (3.21)
for each induced subgraphHof a graphG. LetGbe a nontrivial connected graph andH a connected induced subgraph ofG. Theacyclic partition ratioofHandGis defined by
ra(H, G)=apd(H)
apd(G). (3.22)
Unlike the ratio in (3.21), it need not occur thatra(H, G)≤1. Since apd(K1,m)=mfor allm≥2,G=K1,m, andH=K2, we can make the ratiora(H, G)as small as we wish by choosingmarbitrarily large. Although this may not be surprising, it may be unexpected that, in fact,ra(H, G)can be as large as we wish (see [49]).
Theorem3.20. LetandMbe two real numbers.
(1) There exist a connected graph G and an induced subgraph H of G such that ra(H, G) < .
(2) There exist a connected graphGand an induced subgraphH ofG such that ra(H, G) > M.
4. Conditional resolving decompositions. Adecompositionof a graphGis a collec- tion of subgraphs ofG, none of which has isolated vertices, whose edge sets provide a partition ofE(G). A decomposition intoksubgraphs is ak-decomposition. A decompo- sitionᏰ= {G1, G2, . . . , Gk}isordered if the ordering (G1, G2, . . . , Gk) has been imposed on Ᏸ. If each subgraph Gi (1≤i≤k) is isomorphic to a graphH, then Ᏸ is called an H-decomposition ofG. Decompositions of graphs have been the subject of many studies.
For edgeseandfin a connected graphG, thedistanced(e, f )betweeneandfis the minimum nonnegative integerkfor which there exists a sequencee=e0, e1, . . . , ek=f of edges ofGsuch thateiandei+1are adjacent fori=0,1, . . . , k−1. Thus,d(e, f )=0 if and only ife=f,d(e, f )=1 if and only ifeandfare adjacent, andd(e, f )=2 if and only ifeandf are nonadjacent edges that are adjacent to a common edge ofG. Also, this distance equals the standard distance between verticeseandf in the line graph L(G). For an edgeeofGand a subgraphF ofG, we define the distance betweeneand F as
d(e, F )= min
f∈E(F )d(e, f ). (4.1)
LetᏰ= {G1, G2, . . . , Gk}be an orderedk-decomposition of a connected graphG. For e∈E(G), theᏰ-code(or simply thecode) ofeis thek-vector
cᏰ(e)= d
e, G1 , d
e, G2 , . . . , d
e, Gk
. (4.2)
Hence exactly one coordinate ofcᏰ(e)is 0, namely, theith coordinate ife∈E(Gi). The decompositionᏰis said to be aresolving decompositionforGif every two distinct edges ofGhave distinctᏰ-codes. The minimumkfor whichGhas a resolvingk-decomposition is itsdecomposition dimensiondimd(G). A resolving decomposition ofGwith dimd(G) elements is aminimum resolving decompositionforG.
To illustrate these concepts, consider the graphGofFigure 4.1. LetᏰ= {G1, G2, G3}, whereE(G1)= {e1, e5, f1, f5, f4},E(G2)= {e2, e3, f2}, andE(G3)= {e4, e6, f3, f6, f7}. The Ᏸ-codes of the edges ofGare
cᏰ e1
=(0,1,2), cᏰ e2
=(1,0,2), cᏰ e3
=(2,0,1), cᏰ e4
=(2,1,0), cᏰ
e5
=(0,4,1), cᏰ e6
=(1,4,0), cᏰ f1
=(0,1,1), cᏰ f2
=(1,0,1), cᏰ
f3
=(1,1,0), cᏰ f4
=(0,2,1), cᏰ f5
=(0,3,1), cᏰ f6
=(1,3,0), cᏰ
f7
=(1,2,0).
(4.3) Thus, Ᏸ is a resolving decomposition of G. In fact, there is no 2-element resolving decomposition ofG. Thus,Ᏸis a minimum resolving decomposition, and so dimd(G)=
|Ᏸ| =3.
These concepts were first introduced in [7] and studied further in [25,26,35,36].
4.1. Connected resolving decompositions. A resolving decomposition Ᏸ = {G1, G2, . . . , Gk} of a connected graphG is connected if each subgraph Gi (1≤ i≤k) is a connected subgraph in G. The minimumk for whichG has a connected resolving k-decomposition is itsconnected decomposition dimensioncdimd(G). A connected re- solving decomposition ofGwith cdimd(G) elements is called a minimum connected resolving decomposition ofG. These concepts were introduced and studied in [40,44].
IfGhasm≥2 edges, then them-decompositionᏰ= {G1, G2, . . . , Gm}, where each set E(Gi)(1≤i≤m) consists of a single edge, is a connected resolving decomposition ofG. Thus, cdimd(G)is defined for every connected graphGof size at least 2. More- over, every connected resolvingk-decomposition is a resolvingk-decomposition, and
e6
e5 f6
f5
f7
f4
f1 f2 f3
e1 e2 e3 e4
Figure4.1. A graphGwith dimd(G)=3.
so
2≤dimd(G)≤cdimd(G)≤m (4.4)
for every connected graphGof sizem≥2. Furthermore, all connected graphsGof size m≥4 with cdimd(G)∈ {2, m−2, m−1, m}are characterized in [40].
The next three results [40] present bounds for cdimd(G)of a connected graphGin terms of (1) its size and diameter, (2) its size and girth, (3) its order.
Theorem4.1. IfGis a connected graph of sizem≥2and diameterd, then 1+logd+1m≤cdimd(G)≤m−d+2. (4.5) The upper bound inTheorem 4.1is sharp ford≥2, while the sharpness of the lower bound inTheorem 4.1is unknown.
Theorem4.2. IfGis a connected graph of sizem≥3and girth≥3, then
3≤cdimd(G)≤m−+3. (4.6)
Moreover,cdimd(G)=m−+3if and only ifGis a cycle of order at least3.
For a connected graphG, let mk(G)=min
k(G−T ):Tis a spanning tree ofG
, (4.7)
wherek(G−T )is the number of components ofG−T.
Theorem4.3. IfGis a connected graph of ordern≥5, then
cdimd(G)≤n+mk(G)−1. (4.8)
The upper bound inTheorem 4.3is attainable for stars. On the other hand, strict inequality inTheorem 4.3can hold as well.
The decomposition dimensions of trees that are not paths have been studied in [7, 26], where bounds for them have been determined. However, there is no general formula for the decomposition dimension of a tree that is not a path. On the other
hand, a formula for the connected decomposition dimension of a tree that is not a path was established in [44].
Theorem4.4. IfT is a tree that is not a path, then
cdimd(T )=σ (T )−ex(T )+1. (4.9) Therefore, byTheorem 3.4, ifT is a tree that is not a path, then
cpd(T )=cdimd(T )=σ (T )−ex(T )+1. (4.10) On the other hand, it was shown in [41] that
cpd(G)≥σ (G)−ex(G)+1 (4.11)
for every connected graphG, while this is not true in general for connected decompo- sition dimensions of graphs (see [44]).
We have seen that ifG is a connected graph of size at least 2 with dimd(G)=a and cdimd(G)=b, then 2≤a≤b. Furthermore, the paths of order at least 3 are the only connected graphsGof size at least 2 with dimd(G)=cdimd(G)=2. Thus there is no connected graphGwith dimd(G)=2 and cdimd(G) >2. On the other hand, the following realization result appears in [44].
Theorem4.5. For every paira,bof integers with3≤a≤b, there exists a connected graphGsuch thatdimd(G)=aandcdimd(G)=b.
For a connected graphGof sizem≥2, thedecomposition dimension ratiordim(G)of Gand theconnected decomposition dimension ratiorcd(G)ofGare defined as
rdim(G)=dimd(G)
m , rcd(G)=cdimd(G)
m . (4.12)
Since 2≤dimd(G)≤cdimd(G)≤mfor every connected graphGof sizem≥2, it follows that
0< rdim(G)≤rcd(G)≤1. (4.13) Furthermore,rdim(G)=1 if and only ifrcd(G)=1.
There exist infinitely many triplesa,b,mof integers with 2≤a≤b≤mthat are not realizable as the decomposition dimension, connected decomposition dimension, and size of any connected graph. However, it was shown in [40] that every pairs,tof rational numbers with 0< s≤t <1 is realizable as the decomposition dimension ratio and connected decomposition dimension ratio for some connected graph.
Theorem4.6. For each pairs,tof rational numbers with0< s≤t <1, there is a connected graphGsuch thatrdim(G)=sandrcd(G)=t.
4.2. Independent resolving decompositions. A decompositionᏰ= {G1, G2, . . . , Gk} of a connected graphGis calledindependent ifE(Gi)is independent for eachi(1≤ i≤k) inG. This concept can be considered from an edge-coloring point of view. Recall
that aproper edge coloring(or simply, anedge coloring) of a nonempty graphGis an assignmentcof colors (positive integers) to the edges ofGso that adjacent edges are colored differently, that is,c:E(G)→Nis a mapping such thatc(e)≠c(f )ifeandf are adjacent edges ofG. The minimumkfor which there is an edge coloring ofGusingk distinct colors is called theedge chromatic numberχe(G)ofG. IfᏰ= {G1, G2, . . . , Gk}is an independent decomposition of a graphG, then by assigning colorito all edges inGi
(1≤i≤k), we obtain an edge coloring ofGusingkdistinct colors. On the other hand, if cis an edge coloring of a connected graphG, using the colors 1,2, . . . , kfor some positive integerk, thenc(e)≠c(f )for adjacent edgeseandf inG. Equivalently,cproduces a decompositionᏰofE(G)into color classes (independent sets)C1, C2, . . . , Ck, where the edges ofCiare coloredifor 1≤i≤k. Thus, for an edgeein a graphG, thek-vector
cᏰ(e)= d
e, C1
, d e, C2
, . . . , d e, Ck
(4.14)
is called thecolor code(or simply thecode)cᏰ(e)ofe. If distinct edges ofGhave dis- tinct color codes, thencis called aresolving edge coloring (orindependent resolving decomposition) ofG. Thus a resolving edge coloring ofGis an edge coloring that dis- tinguishes all edges ofGin terms of their distances from the resulting color classes. A minimum resolving edge coloringuses a minimum number of colors, and this number is theresolving edge chromatic number χre(G)ofG. These concepts were introduced and studied in [17,47].
Suppose that E(G)= {e1, e2, . . . , em}, where m≥ 2. By assigning color ito ei for 1≤i≤m, we obtain a resolving edge coloring ofG. Thus,χre(G)is defined for every graphG. Moreover, every resolving edge coloring is an edge coloring and every resolving edge coloring is a resolving decomposition. Therefore,
2≤max
dimd(G), χe(G)
≤χre(G)≤m (4.15)
for each connected graphGof sizem≥2. It was shown in [17] that every pairk,m of integers with 3≤k≤mis realizable as the resolving edge chromatic number and size of some connected graph. Furthermore, characterizations of all connected graphs Gwithχre(G)=2,3, mhave been established in [17].
Theorem4.7. LetGbe a connected graph of ordern≥3and sizem. Then (a) χre(G)=2if and only ifG=P3;
(b) χre(G)=3if and only ifn≥4and(i)G=Pn,(ii)G=Cn, wherenis odd, or(iii) G∈᐀∪ᐁ, where᐀is the set of all treesTwith∆(T )=3having exactly one vertex of degree3andᐁis the set of all unicyclic graphsG with∆(G)=3having an even cycle and exactly one vertex of degree3;
(c) χre(G)=m if and only ifG∈ {K3, P4, P3∪K1, C4, K4−e, K4}or n≥5andG= K1,n−1.
Resolving edge chromatic numbers of paths, stars, and cycles were determined in [17] and the edge chromatic numbers of complete graphs and trees were studied in [17,47], where upper bounds for the resolving edge chromatic number of a connected
graph are established in terms of (1) its size and diameter, (2) its size and girth, (3) its order and edge chromatic number, (4) its decomposition dimension and edge chromatic number.
Theorem4.8. IfGis a connected graph of sizem≥3and diameterd, then
χre(G)≤m−d+3. (4.16)
Moreover,χre(G)=m−d+3if and only ifGis a path of sizem≥3.
Theorem4.9. IfGis a connected graph of sizemand girth, wherem≥≥3, then
χre(G)≤
m−+3 ifis odd,
m−+4 ifis even. (4.17)
Furthermore,χre(G)=m−+4if and only ifG=Cnfor some evenn≥4.
IfG=Cnfor some odd integern, then=m=n, and soχre(G)=m−+3. However, the odd cycles are not the only connected graphsGof sizem≥3 having girth≥3 andχre(G)=m−+3.
Theorem4.10. IfGis a connected graph of ordern≥5, then
χe(G)≤χre(G)≤n+χe(G)−1. (4.18) Theorem4.11. IfGis a connected graph of ordern≥5, then
χre(G)≤n+k−1, (4.19)
wherek=min{χe(E(G)−E(T )):T is a spanning tree ofG}.
It is known that∆(G)≤χe(G)≤∆(G)+1 for every nonempty graphG, where the upper bound is due to Vizing [53]. Thus, ifGis a connected graph of ordern≥5, then
∆(G)≤χre(G)≤n+∆(G). (4.20) However, just how good the upper bounds are in Theorems4.10and4.11and (4.20) is not known.
References
[1] R. C. Brigham, G. Chartrand, R. D. Dutton, and P. Zhang,Isometric embeddings of bipartite graphs, Congr. Numer.154(2002), 7–12.
[2] ,Resolving domination in graphs, Math. Bohem.128(2003), no. 1, 25–36.
[3] P. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang,Onk-dimensional graphs and their bases, Period. Math. Hungar.46(2003), no. 1, 9–15.
[4] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann,Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math.105(2000), no. 1–3, 99–113.
[5] G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater, and P. Zhang,The locating-chromatic number of a graph, Bull. Inst. Combin. Appl.36(2002), 89–101.
[6] ,Graphs of ordernwith locating-chromatic numbern−1, Discrete Math.269(2003), no. 1–3, 65–79.
[7] G. Chartrand, D. Erwin, M. Raines, and P. Zhang,The decomposition dimension of graphs, Graphs Combin.17(2001), no. 4, 599–605.
[8] G. Chartrand, D. Erwin, P. J. Slater, and P. Zhang,Distance-location numbers of graphs, Util.
Math.63(2003), 65–79.
[9] G. Chartrand, T. W. Haynes, M. A. Henning, and P. Zhang,Stratified claw domination in prisms, J. Combin. Math. Combin. Comput.33(2000), 81–96.
[10] ,Stratification and domination in graphs, Discrete Math.272(2003), no. 2-3, 171–
185.
[11] G. Chartrand and H. V. Kronk,The point-arboricity of planar graphs, J. London Math. Soc.
44(1969), 612–616.
[12] G. Chartrand, H. V. Kronk, and C. E. Wall,The point-arboricity of a graph, Israel J. Math.6 (1968), 169–175.
[13] G. Chartrand and L. Lesniak,Graphs & Digraphs, 3rd ed., Chapman & Hall, London, 1996.
[14] G. Chartrand, C. Poisson, and P. Zhang,Resolvability and the upper dimension of graphs, Comput. Math. Appl.39(2000), no. 12, 19–28.
[15] G. Chartrand, M. Raines, and P. Zhang,The directed distance dimension of oriented graphs, Math. Bohem.125(2000), no. 2, 155–168.
[16] ,On the dimension of oriented graphs, Util. Math.60(2001), 139–151.
[17] G. Chartrand, V. Saenpholphat, and P. Zhang,Resolving edge colorings in graphs, to appear in Ars Combin.
[18] ,The independent resolving number of a graph, Math. Bohem.128(2003), no. 4, 379–393.
[19] G. Chartrand, E. Salehi, and P. Zhang,The partition dimension of a graph, Aequationes Math.59(2000), no. 1-2, 45–54.
[20] G. Chartrand and P. Zhang,On the chromatic dimension of a graph, Congr. Numer.145 (2000), 97–108.
[21] ,The forcing dimension of a graph, Math. Bohem.126(2001), no. 4, 711–720.
[22] ,The theory and applications of resolvability in graphs. A survey, Congr. Numer.160 (2003), 47–68.
[23] G. Chartrand, P. Zhang, and E. Salehi,On the partition dimension of a graph, Congr. Numer.
130(1998), 157–168.
[24] J. Currie and O. R. Oellermann,The metric dimension and metric independence of a graph, J. Combin. Math. Combin. Comput.39(2001), 157–167.
[25] H. Enomoto,Upper bound of the decomposition dimension of a graph, Congr. Numer.145 (2000), 157–160.
[26] H. Enomoto and T. Nakamigawa,On the decomposition dimension of trees, Discrete Math.
252(2002), no. 1–3, 219–225.
[27] M. R. Garey and D. S. Johnson,Computers and Intractability. A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman, California, 1979.
[28] F. Harary and R. A. Melter,On the metric dimension of a graph, Ars Combin.2(1976), 191–195.
[29] B. L. Hulme, A. W. Shiver, and P. J. Slater,Fire: a Subroutine for Fire Protection Network Analysis, Sandia National Laboratories, New Mexico, 1981, SAND 81-1261.
[30] ,Computing Minimum Cost Fire Protection, Sandia National Laboratories, New Mex- ico, 1982, SAND 82-0809.
[31] , A Boolean algebraic analysis of fire protection, Algebraic and Combinatorial Methods in Operations Research, North-Holland Math. Stud., vol. 95, North-Holland Publishing, Amsterdam, 1984, pp. 215–227.
[32] M. A. Johnson,Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist3(1993), 203–236.
[33] ,Browsable structure-activity datasets, Advances in Molecular Similarity (R. Carbó- Dorca and P. Mezey, eds.), JAI Press, Connecticut, 1998, pp. 153–170.
