Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: resolving partition

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Connected partition dimensions of graphs

100%

Saenpholphat V., Zhang P.

Discussiones Mathematicae Graph Theory

2002

tom 22

nr 2

305-323

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Saenpholphat V.

1 Zhang P.

1 2002

Wyniki wyszukiwania

Connected partition dimensions of graphs