On Connected Resolving Decompositions in Graphs |
| |
Authors: | Varaporn Saenpholphat Ping Zhang |
| |
Affiliation: | (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, Gi) is the distance from e to Gi. 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 dimd(G). A resolving decomposition of G is connected if each Gi 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 dimd(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 dimd(G)/m = s and cd(G)/m = t. |
| |
Keywords: | distance resolving decomposition connected resolving decomposition |
本文献已被 SpringerLink 等数据库收录! |
|