PDF
Discussiones
Mathematicae Graph Theory 22(2) (2002) 305-323
DOI: https://doi.org/10.7151/dmgt.1177
CONNECTED PARTITION DIMENSIONS OF GRAPHS
Varaporn Saenpholphat and Ping Zhang
Department of Mathematics and Statistics
Western Michigan University
Kalamozoo, MI 49008, USA
Abstract
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 ∈ S}. For an ordered k-partition Π={S1,S2,…,Sk} of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v,S1), d(v,S2),…, d(v,Sk)). The k-partition Π is a resolving partition if the k-vectors r(v|Π), v ∈ 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. A resolving partition Π = {S1,S2,…,Sk} of V(G) is connected if each subgraph 〈Si〉 induced by Si (1 ≤ i ≤ k) is connected in G. The minimum k for which there is a connected resolving k-partition of V(G) is the connected partition dimension cpd(G) of G. Thus 2 ≤ pd (G) ≤cpd(G) ≤ n for every connected graph G of order n≥2. The connected partition dimensions of several classes of well-known graphs are determined. It is shown that for every pair a, b of integers with 3≤a≤b≤2a−1, there is a connected graph G having pd(G) = a and cpd(G) = b. Connected graphs of order n ≥ 3 having connected partition dimension 2, n, or n−1 are characterized.Keywords: distance, resolving partition, connected resolving partition.
2000 Mathematics Subject Classification: 05C12.
References
[1] | G. Chartrand and L. Lesniak, Graphs & Digraphs, third edition (Chapman & Hall, New York, 1996). |
[2] | G. Chartrand, C. Poisson and P. Zhang, Resolvability and the upper dimension of graphs, Inter. J. Comput. Math. Appl. 39 (2000) 19-28, doi: 10.1016/S0898-1221(00)00126-7. |
[3] | G. Chartrand, E. Salehi and P. Zhang, On the partition dimension of a graph, Congress. Numer. 131 (1998) 55-66. |
[4] | G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000) 45-54, doi: 10.1007/PL00000127. |
[5] | F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195. |
[6] | M.A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist. 3 (1993) 203-236, doi: 10.1080/10543409308835060. |
[7] | M.A. Johnson, Browsable structure-activity datasets, preprint. |
[8] | P.J. Slater, Leaves of trees, Congress. Numer. 14 (1975) 549-559. |
[9] | P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988) 445-455. |
Received 24 April 2001
Revised 20 October 2001
Close