On Connected Resolving Decompositions in Graphs |
| |
Authors: | Varaporn Saenpholphat Ping Zhang |
| |
Institution: | (1) Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, U.S.A |
| |
Abstract: | For an ordered k-decomposition
of a connected graph G and an edge e of G, the
-code of e is the k-tuple
where d(e, G
i) is the distance from e to G
i. A decomposition
is resolving if every two distinct edges of G have distinct
-codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim
d
(G). A resolving decomposition
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. |
| |
Keywords: | distance resolving decomposition connected resolving decomposition |
本文献已被 SpringerLink 等数据库收录! |
|