- Tytuł:
- Closed k-stop distance in graphs
- Autorzy:
-
Bullington, Grady
Eroh, Linda
Gera, Ralucca
Winters, Steven - Powiązania:
- https://bibliotekanauki.pl/articles/743969.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Traveling Salesman
Steiner distance
distance
closed k-stop distance - Opis:
-
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. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2011, 31, 3; 533-545
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł