# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## Closed k-stop distance in graphs

 Grady Bullington1, Linda Eroh1, Ralucca Gera2 and Steven J. Winters1 1Department of Mathematics University of Wisconsin Oshkosh Oshkosh, WI 54901 USA 2Department of Applied Mathematics Naval Postgraduate School Monterey, CA 93943 USA

## Abstract

The Traveling Salesman Problem (TSP) is still one of the most researched topics in computational mathematics, and we introduce a variant of it, namely the study of the closed k-walks in graphs. We search for a shortest closed route visiting k cities in a non complete graph without weights. This motivates the following definition. Given a set of k distinct vertices S = { x1, x2, …,xk } in a simple graph G, the closed k-stop-distance of set S is defined to be
 dk (S) = min Θ ∈ P(S) ⎛⎜⎝ d( Θ(x1), Θ(x2)) + d( Θ(x2), Θ(x3)) + …+ d( Θ(xk), Θ(x1)) ⎞⎟⎠ ,

where P(S) is the set of all permutations from S onto S. That is the same as saying that dk (S) is the length of the shortest closed walk through the vertices {x1, …,xk}. 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 k-stop distance.

The closed 2-stop distance is twice the ordinary distance between two vertices. We conjecture that radk(G) ≤ diamk(G) ≤ k/(k −1) radk(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 3-eccentricity between rad3(G) and diam3(G). We also study the closed k-stop center and closed k-stop periphery of a graph, for k = 3.

Keywords: Traveling Salesman, Steiner distance, distance, closed k-stop distance

2010 Mathematics Subject Classification: 05C12, 05C05.

## References

  G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004).  G. Chartrand, O.R. Oellermann, S. Tian and H.-B. Zou, Steiner distance in graphs, Casopis Pro Pestován'i Matematiky 114 (1989) 399--410.  J. Gadzinski, P. Sanders, and V. Xiong, k-stop-return distances in graphs, unpublished manuscript.  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), 393--403.  M.A. Henning, O.R. Oellermann, and H.C. Swart, On the Steiner Radius and Steiner Diameter of a Graph. Ars Combin. 29C (1990) 13--19.  O.R. Oellermann, On Steiner Centers and Steiner Medians of Graphs, Networks 34 (1999) 258--263, doi: 10.1002/(SICI)1097-0037(199912)34:4<258::AID-NET4>3.0.CO;2-2.