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:
“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.
““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)
“Though trees turn bare and girls turn wives,
We shall afford our costly seasons;
There is a gentleness survives
That will outspeak and has its reasons.
There is a loveliness exists,
Preserves us, not for specialists.”
—William Dewitt Snodgrass (b. 1926)