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:
“In some of those dense fir and spruce woods there is hardly room for the smoke to go up. The trees are a standing night, and every fir and spruce which you fell is a plume plucked from night’s raven wing.”
—Henry David Thoreau (1817–1862)
“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)
“the broad cloud-driving moon in the clear sky
Lifts o’er the firs her shining shield,
And in her tranquil light
Sleep falls on forest and field.
See! sleep hath fallen: the trees are asleep:
The night is come. The land is wrapt in sleep.”
—Robert Bridges (1844–1930)