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:
“The quality of moral behaviour varies in inverse ratio to the number of human beings involved.”
—Aldous Huxley (1894–1963)
“Most childhood problems don’t result from “bad” parenting, but are the inevitable result of the growing that parents and children do together. The point isn’t to head off these problems or find ways around them, but rather to work through them together and in doing so to develop a relationship of mutual trust to rely on when the next problem comes along.”
—Fred Rogers (20th century)