Connected partition dimensions of graphs

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 -