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:
“Out of the woods my Master came,
Content with death and shame.
When Death and Shame would woo Him last,
From under the trees they drew Him last:
Twas on a tree they slew Himlast
When out of the woods He came.”
—Sidney Lanier (18421881)
“At twelve, the disintegration of afternoon
Began, the return to phantomerei, if not
To phantoms. Till then, it had been the other way:
One imagined the violet trees but the trees stood green,
At twelve, as green as ever they would be.
The sky was blue beyond the vaultiest phrase.”
—Wallace Stevens (18791955)
“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 (18741963)