Some Open Problems in Graph Theory

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

diam_n T <= [n/(n-1)] rad_nT 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.

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