Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Closed k-stop distance in graphs

100%

Bullington G., Eroh L., Gera R., Winters S.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 3

533-545

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.

Domination in functigraphs

88%

Eroh L., Gera R., Kang C., Larson C., Yi E.

Discussiones Mathematicae Graph Theory

2012

tom 32

nr 2

299-319

Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a generalized prism) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let γ(G) denote the domination number of G. It is readily seen that γ(G) ≤ γ(C(G,f)) ≤ 2 γ(G). We investigate for graphs generally, and for cycles in great detail, the functions which achieve the upper and lower bounds, as well as the realization of the intermediate values.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Eroh L.

2 Gera R.

1 Bullington G.

1 Kang C.

1 Larson C.

1 Winters S.

1 Yi E.

1 2012

1 2011

Wyniki wyszukiwania

Closed k-stop distance in graphs

Domination in functigraphs