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:
“Let us have a good many maples and hickories and scarlet oaks, then, I say. Blaze away! Shall that dirty roll of bunting in the gun-house be all the colors a village can display? A village is not complete, unless it have these trees to mark the season in it. They are important, like the town clock. A village that has them not will not be found to work well. It has a screw loose, an essential part is wanting.”
—Henry David Thoreau (1817–1862)
“It was when the trees were leafless first in November
And their blackness became apparent, that one first
Knew the eccentric to be the base of design.”
—Wallace Stevens (1879–1955)
“I am a rose of Sharon, a lily of the valleys. As a lily among brambles, so is my love among maidens. As an apple tree among the trees of the wood, so is my beloved among young men. With great delight I sat in his shadow, and his fruit was sweet to my taste.”
—Bible: Hebrew, Song of Solomon 2:1-3.