# Connected partition dimensions of graphs

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

top

## Abstract

top
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.

## How to cite

top

Varaporn 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. [1] G. Chartrand and L. Lesniak, Graphs & Digraphs, third edition (Chapman & Hall, New York, 1996).
2. [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. [3] G. Chartrand, E. Salehi and P. Zhang, On the partition dimension of a graph, Congress. Numer. 131 (1998) 55-66. Zbl0952.05021
4. [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. [5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195. Zbl0349.05118
6. [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. [7] M.A. Johnson, Browsable structure-activity datasets, preprint.
8. [8] P.J. Slater, Leaves of trees, Congress. Numer. 14 (1975) 549-559.
9. [9] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988) 445-455. Zbl0656.05057

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.