# Some Open Problems in Graph Theory

1. It has been shown by Chartrand, Oellermann, Tian, and Zou that, for a tree T:

diamn T <= [n/(n-1)] radn 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:

diamn 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.

2. It was shown by Oellermann and Tian that for a tree T:

Cn-1(T) is contained in Cn (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.

3. It was shown by Beineke, Oellermann and Pippert that if T is a tree, then

Mn-1(T) is contained in Mn (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.

4. 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.

5. 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.