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)
“It is very comforting to believe that leaders who do terrible things are, in fact, mad. That way, all we have to do is make sure we don’t put psychotics in high places and we’ve got the problem solved.”
—Tom Wolfe (b. 1931)