Discussiones Mathematicae Graph Theory 31(3) (2011)
533545
doi: 10.7151/dmgt.1563
Grady Bullington^{1}, Linda Eroh^{1}, Ralucca Gera^{2} and Steven J. Winters^{1}
^{1}Department of Mathematics 

where P(S) is the set of all permutations from S onto S. That is the same as saying that d_{k} (S) is the length of the shortest closed walk through the vertices {x_{1}, …,x_{k}}. Recall that the Steiner distance sd(S) is the number of edges in a minimum connected subgraph containing all of the vertices of S. We note some relationships between Steiner distance and closed kstop distance.
The closed 2stop distance is twice the ordinary distance between two vertices. We conjecture that rad_{k}(G) ≤ diam_{k}(G) ≤ k/(k −1) rad_{k}(G) for any connected graph G for k ≤ 2. For k = 2, this formula reduces to the classical result rad(G) ≤ diam(G) ≤ 2 rad(G). We prove the conjecture in the cases when k = 3 and k = 4 for any graph G and for k ≤ 3 when G is a tree. We consider the minimum number of vertices with each possible 3eccentricity between rad_{3}(G) and diam_{3}(G). We also study the closed kstop center and closed kstop periphery of a graph, for k = 3.
Keywords: Traveling Salesman, Steiner distance, distance, closed kstop distance
2010 Mathematics Subject Classification: 05C12, 05C05.
[1]  G. Chartrand and P. Zhang, Introduction to Graph Theory (McGrawHill, Kalamazoo, MI, 2004). 
[2]  G. Chartrand, O.R. Oellermann, S. Tian and H.B. Zou, Steiner distance in graphs, Casopis Pro Pestován'i Matematiky 114 (1989) 399410. 
[3]  J. Gadzinski, P. Sanders, and V. Xiong, kstopreturn distances in graphs, unpublished manuscript. 
[4]  M.A. Henning, O.R. Oellermann, and H.C. Swart, On Vertices with Maximum Steiner [eccentricity in graphs]. Graph Theory, Combinatorics, Algorithms, and Applications (San Francisco, CA, (1989)). SIAM, Philadelphia, PA (1991), 393403. 
[5]  M.A. Henning, O.R. Oellermann, and H.C. Swart, On the Steiner Radius and Steiner Diameter of a Graph. Ars Combin. 29C (1990) 1319. 
[6]  O.R. Oellermann, On Steiner Centers and Steiner Medians of Graphs, Networks 34 (1999) 258263, doi: 10.1002/(SICI)10970037(199912)34:4<258::AIDNET4>3.0.CO;22. 
Received 4 June 2009
Revised 6 August 2010
Accepted 6 August 2010