PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 3 | 533-545
Tytuł artykułu

Closed k-stop distance in graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
31
Numer
3
Strony
533-545
Opis fizyczny
Daty
wydano
2011
otrzymano
2009-06-04
poprawiono
2010-08-06
zaakceptowano
2010-08-06
Twórcy
  • Department of Mathematics, University of Wisconsin Oshkosh, Oshkosh, WI 54901 USA
autor
  • Department of Mathematics, University of Wisconsin Oshkosh, Oshkosh, WI 54901 USA
autor
  • Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943 USA
  • Department of Mathematics University of Wisconsin Oshkosh, Oshkosh, WI 54901 USA
Bibliografia
  • [1] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004).
  • [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.
  • [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
  • [7] O.R. Oellermann, Steiner Centers in Graphs, J. Graph Theory 14 (1990) 585–597.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1563
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.