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:
“As great trees attract the winds, so great fame attracts envy.”
—Chinese proverb.
“But, where the road runs near the stream,
Oft through the trees they catch a glance
Of passing troops in the sun’s beam—
Pennon, and plume, and flashing lance!
Forth to the world those soldiers fare,
To life, to cities, and to war!”
—Matthew Arnold (1822–1888)
“Why are there trees I never walk under but large and melodious thoughts descend upon me?”
—Walt Whitman (1819–1892)