On Connected Resolving Decompositions in Graphs
Varaporn Saenpholphat, Ping Zhang · Czechoslovak Mathematical Journal · 2004
For an ordered k-decomposition $$D = \{ G_1 ,G_2 ,...,G_k \} $$ of a connected graph G and an edge e of G, the $$D$$ -code of e is the k-tuple $$c_D (e) = (d(e,G_1 ),d(e,G_2 ),...,d(e,G_k ))$$ where d(e, G i) is the distance from e to G i. A decomposition $$D$$ is resolving if every two distinct edges of G have distinct $$D$$ -codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim d (G). A resolving decomposition $$D$$ of G is connected if each G i is connected for 1 ≤ i ≤ k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 ≤ dim d (G) ≤ cd(G) ≤ m for every connected graph G of size m ≥ 2. All nontrivial connected graphs of size m with connected decomposition number 2 or m have been characterized. We present characterizations for connected graphs of size m with connected decomposition number m − 1 or m − 2. It is shown that each pair s, t of rational numbers with 0 < s ≤ t ≤ 1, there is a connected graph G of size m such that dim d (G)/m = s and cd(G)/m = t.