- It has been shown by Chartrand,
Oellermann, Tian, and Zou that, for a tree T:
diam _{n}T <= [n/(n-1)] rad_{n }T for all n>=2.

This inequality does not hold for graphs in general as was shown by Henning, Oellermann, and Swart. It was shown in the same paper that for a graph G and n=3 and 4:diam _{n}G <= [2(n-1)/(2n-1)] rad_{ n}G.It was conjectured in the same paper that this inequality holds for all n >= 3. However, it remains an open problem for n >=5.

- It was shown by Oellermann
and Tian that for a tree T:
C _{n-1}(T) is contained in C_{n }(T) for all n >=3.It remains an open problem to determine whether this containment holds for general graphs. In other words, it is not known if the Steiner (n-1)-center of a graph is contained in its Steiner n-center.

- It was shown by Beineke,
Oellermann and Pippert that if T is a tree, then
M _{n-1}(T) is contained in M_{n }(T) for all n >= 3.It remains an open problem to determine whether this containment holds for general graphs. In other words, it is not known if the Steiner (n-1)-median of a graph is contained in its Steiner n-median.

- It is known that for a given n >= 2 every graph is the Steiner n-center of some graph. (Also, the Steiner n-centers of trees were characterized by Oellermann and Tian). It is known that every graph is the 2-median of some graph (see Holbert,and Hendry). Steiner n-medians of trees have been completely characterized by Beineke, Oellermann, and Pippert. However, it remains an open problem to determine which graphs are Steiner n-medians of graphs for n >= 3.
- It was shown by Oellermann that Steiner n-centers and Steiner n-medians of trees can be specified according to their characterizations and that they can be arbitrarily far apart. Holbert... showed that the 2-center and 2-median of a graph can be specified and that these can be arbitrarily far apart in some graph. However, for n > 2, this problem is still open. Of course, solving this problem can only be attempted once problem 4 has been solved.

Copyright © 1998. Ortrud Oellermann

**URL: http://www.uwinnipeg.ca/~ooellerm/open_problems/index.html
**