Trees
Slater (1975) provides the following simple characterization of the metric dimension of a tree. If the tree is a path, its metric dimension is one. Otherwise, let L denote the set of degree-one vertices in the tree (usually called leaves, although Slater uses that word differently). Let K be the set of vertices that have degree greater than two, and that are connected by paths of degree-two vertices to one or more leaves. Then the metric dimension is |L| − |K|. A basis of this cardinality may be formed by removing from L one of the leaves associated with each vertex in K.
Read more about this topic: Metric Dimension (graph Theory)
Famous quotes containing the word trees:
““A thousand Christmas trees! at what apiece?”
He felt some need of softening that to me:
“A thousand trees would come to thirty dollars.”
Then I was certain I had never meant
To let him have them.”
—Robert Frost (1874–1963)
“It is as when a migrating army of mice girdles a forest of pines. The chopper fells trees from the same motive that the mouse gnaws them,—to get his living. You tell me that he has a more interesting family than the mouse. That is as it happens.”
—Henry David Thoreau (1817–1862)
“Usually the scenery about them is drear and savage enough; and the logger’s camp is as completely in the woods as a fungus at the foot of a pine in a swamp; no outlook but to the sky overhead; no more clearing than is made by cutting down the trees of which it is built, and those which are necessary for fuel.”
—Henry David Thoreau (1817–1862)