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)
“In the nineteenth century the problem was that God is dead; in the twentieth century the problem is that man is dead.”
—Erich Fromm (1900–1980)