# Closed k-stop distance in graphs

Grady Bullington; Linda Eroh; Ralucca Gera; Steven J. Winters

Discussiones Mathematicae Graph Theory (2011)

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

## Access Full Article

top## Abstract

top## How to cite

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

@article{GradyBullington2011,

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] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004). Zbl1096.05001
- [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] J. Gadzinski, P. Sanders, and V. Xiong, k-stop-return 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), 393-403. Zbl0735.05035
- [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] 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] O.R. Oellermann, Steiner Centers in Graphs, J. Graph Theory 14 (1990) 585–597. Zbl0721.05035

## NotesEmbed ?

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