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:
“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)
“Your soul ... is a dark forest. But the trees are of a particular species, they are genealogical trees.”
—Marcel Proust (1871–1922)
“Any walk through a park that runs between a double line of mangy trees and passes brazenly by the ladies’ toilet is invariably known as “Lover’s Lane.””
—F. Scott Fitzgerald (1896–1940)