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)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)