The Decomposition Dimension of Graphs |
| |
Authors: | Gary Chartrand David Erwin Michael Raines Ping Zhang |
| |
Institution: | (1) Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA., US;(2) Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA. e-mail: chartrand@wmich.edu, US;(3) Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA. e-mail: raines@math-stat.wmich.edu, US |
| |
Abstract: | For an ordered k-decomposition ? = {G
1, G
2,…,G
k
} of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(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 ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K
n
) ≤⌊(2n + 5)/3⌋ for n≥ 3.
Received: June 17, 1998 Final version received: August 10, 1999 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|