# Closed k-stop distance in graphs

• Volume: 31, Issue: 3, page 533-545
• ISSN: 2083-5892

top

## Abstract

top
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 = x₁, x₂, ...,xₖ in a simple graph G, the closed k-stop-distance of set is defined to be $dₖ\left(\right)=mi{n}_{\Theta \in \left(\right)}\left(d\left(\Theta \left(x₁\right),\Theta \left(x₂\right)\right)+d\left(\Theta \left(x₂\right),\Theta \left(x₃\right)\right)+...+d\left(\Theta \left(xₖ\right),\Theta \left(x₁\right)\right)\right)$, where () is the set of all permutations from onto . That is the same as saying that dₖ() is the length of the shortest closed walk through the vertices x₁, ...,xₖ. Recall that the Steiner distance sd() is the number of edges in a minimum connected subgraph containing all of the vertices of . 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 radₖ(G) ≤ diamₖ(G) ≤ k/(k -1) radₖ(G) for any connected graph G for k ≤ 2. For k = 2, this formula reduces to the classical result rad(G) ≤ diam(G) ≤ 2rad(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 rad₃(G) and diam₃(G). We also study the closed k-stop center and closed k-stop periphery of a graph, for k = 3.

## How to cite

top

Grady Bullington, et al. "Closed k-stop distance in graphs." Discussiones Mathematicae Graph Theory 31.3 (2011): 533-545. <http://eudml.org/doc/270950>.

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 = x₁, x₂, ...,xₖ in a simple graph G, the closed k-stop-distance of set is defined to be $dₖ() = min_\{Θ ∈ ()\} (d(Θ(x₁),Θ(x₂)) + d(Θ(x₂),Θ(x₃)) + ...+ d(Θ(xₖ),Θ(x₁)))$, where () is the set of all permutations from onto . That is the same as saying that dₖ() is the length of the shortest closed walk through the vertices x₁, ...,xₖ. Recall that the Steiner distance sd() is the number of edges in a minimum connected subgraph containing all of the vertices of . 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 radₖ(G) ≤ diamₖ(G) ≤ k/(k -1) radₖ(G) for any connected graph G for k ≤ 2. For k = 2, this formula reduces to the classical result rad(G) ≤ diam(G) ≤ 2rad(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 rad₃(G) and diam₃(G). We also study the closed k-stop center and closed k-stop periphery of a graph, for k = 3.},
author = {Grady Bullington, Linda Eroh, Ralucca Gera, Steven J. Winters},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Traveling Salesman; Steiner distance; distance; closed k-stop distance; traveling salesman; closed -stop distance},
language = {eng},
number = {3},
pages = {533-545},
title = {Closed k-stop distance in graphs},
url = {http://eudml.org/doc/270950},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Grady Bullington
AU - Linda Eroh
AU - Ralucca Gera
AU - Steven J. Winters
TI - Closed k-stop distance in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 3
SP - 533
EP - 545
AB - 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 = x₁, x₂, ...,xₖ in a simple graph G, the closed k-stop-distance of set is defined to be $dₖ() = min_{Θ ∈ ()} (d(Θ(x₁),Θ(x₂)) + d(Θ(x₂),Θ(x₃)) + ...+ d(Θ(xₖ),Θ(x₁)))$, where () is the set of all permutations from onto . That is the same as saying that dₖ() is the length of the shortest closed walk through the vertices x₁, ...,xₖ. Recall that the Steiner distance sd() is the number of edges in a minimum connected subgraph containing all of the vertices of . 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 radₖ(G) ≤ diamₖ(G) ≤ k/(k -1) radₖ(G) for any connected graph G for k ≤ 2. For k = 2, this formula reduces to the classical result rad(G) ≤ diam(G) ≤ 2rad(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 rad₃(G) and diam₃(G). We also study the closed k-stop center and closed k-stop periphery of a graph, for k = 3.
LA - eng
KW - Traveling Salesman; Steiner distance; distance; closed k-stop distance; traveling salesman; closed -stop distance
UR - http://eudml.org/doc/270950
ER -

## References

top
1. [1] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004). Zbl1096.05001
2. [2] 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.
3. [3] J. Gadzinski, P. Sanders, and V. Xiong, k-stop-return distances in graphs, unpublished manuscript.
4. [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), 393-403. Zbl0735.05035
5. [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) 13-19.
6. [6] 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 Zbl0968.05027
7. [7] O.R. Oellermann, Steiner Centers in Graphs, J. Graph Theory 14 (1990) 585–597. Zbl0721.05035

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.