Closed k-stop distance in graphs

Grady 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 -