Inverse Problem
Gutman & Yeh (1995) considered the problem of determining which numbers can be represented as the Wiener index of a graph. They showed that all but two positive integers have such a representation; the two exceptions are the numbers 2 and 5, which are not the Wiener index of any graph. For graphs that must be bipartite, they found that again almost all integers can be represented, with a larger set of exceptions: none of the numbers in the set
- {2, 3, 5, 6, 7, 11, 12, 13, 15, 17, 19, 33, 37, 39}
can be represented as the Wiener index of a bipartite graph.
Gutman and Yeh conjectured, but were unable to prove, a similar description of the numbers that can be represented as Wiener indices of trees, with a set of 49 exceptional values. The conjecture was later proven by Wagner, Wang, and Yu.
Read more about this topic: Wiener Index
Famous quotes containing the words inverse and/or problem:
“Yet time and space are but inverse measures of the force of the soul. The spirit sports with time.”
—Ralph Waldo Emerson (1803–1882)
“But a problem occurs about nothing. For that from which something is made is a cause of the thing made from it; and, necessarily, every cause contributes some assistance to the effect’s existence.”
—Anselm of Canterbury (1033–1109)