- Tytuł:
- Connected partition dimensions of graphs
- Autorzy:
-
Saenpholphat, Varaporn
Zhang, Ping - Tematy:
-
distance
resolving partition
connected resolving partition - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/743364.pdf Link otwiera się w nowym oknie
- Opis:
- 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 Π = {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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł