# Connected partition dimensions of graphs

Varaporn Saenpholphat; Ping Zhang

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 2, page 305-323
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topVaraporn Saenpholphat, and Ping Zhang. "Connected partition dimensions of graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 305-323. <http://eudml.org/doc/270458>.

@article{VarapornSaenpholphat2002,

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) = mind(v,x)|x ∈ S. For an ordered k-partition Π = S₁,S₂,...,Sₖ of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v,S₁), d(v,S₂),..., d(v,Sₖ)). 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 Π = S₁,S₂,...,Sₖ of V(G) is connected if each subgraph $⟨S_i⟩$ induced by $S_i$ (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.},

author = {Varaporn Saenpholphat, Ping Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {distance; resolving partition; connected resolving partition},

language = {eng},

number = {2},

pages = {305-323},

title = {Connected partition dimensions of graphs},

url = {http://eudml.org/doc/270458},

volume = {22},

year = {2002},

}

TY - JOUR

AU - Varaporn Saenpholphat

AU - Ping Zhang

TI - Connected partition dimensions of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 2

SP - 305

EP - 323

AB - 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) = mind(v,x)|x ∈ S. For an ordered k-partition Π = S₁,S₂,...,Sₖ of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v,S₁), d(v,S₂),..., d(v,Sₖ)). 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 Π = S₁,S₂,...,Sₖ of V(G) is connected if each subgraph $⟨S_i⟩$ induced by $S_i$ (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.

LA - eng

KW - distance; resolving partition; connected resolving partition

UR - http://eudml.org/doc/270458

ER -

## References

top- [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. Zbl0953.05021
- [3] G. Chartrand, E. Salehi and P. Zhang, On the partition dimension of a graph, Congress. Numer. 131 (1998) 55-66. Zbl0952.05021
- [4] G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000) 45-54, doi: 10.1007/PL00000127. Zbl0939.05029
- [5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195. Zbl0349.05118
- [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. Zbl0656.05057