Wyniki wyszukiwania

1

The Steiner Wiener Index of A Graph

100%

Li X., Mao Y., Gutman I.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 2

455-465

EN

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = ∑u,v∈V(G) d(u, v) where dG(u, v) is the distance between vertices u and v of G. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and S ⊆ V (G), the Steiner distance d(S) of the vertices of S is the minimum size of a connected subgraph whose vertex set is S. We now introduce the concept of the Steiner Wiener index of a graph. The Steiner k-Wiener index SWk(G) of G is defined by [...] . Expressions for SWk for some special graphs are obtained. We also give sharp upper and lower bounds of SWk of a connected graph, and establish some of its properties in the case of trees. An application in chemistry of the Steiner Wiener index is reported in our another paper.

2

Inverse Problem on the Steiner Wiener Index

100%

Li X., Mao Y., Gutman I.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 38

|

nr 1

83-95

EN

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) =∑u,v∈V (G) dG(u, v), where dG(u, v) is the distance (the length a shortest path) between the vertices u and v in G. For S ⊆ V (G), the Steiner distance d(S) of the vertices of S, introduced by Chartrand et al. in 1989, is the minimum size of a connected subgraph of G whose vertex set contains S. The k-th Steiner Wiener index SWk(G) of G is defined as [...] SWk(G)=∑S⊆V(G)|S|=kd(S) $SW_k (G) = \sum\nolimits_{\mathop {S \subseteq V(G)}\limits_{|S| = k} } {d(S)}$ . We investigate the following problem: Fixed a positive integer k, for what kind of positive integer w does there exist a connected graph G (or a tree T) of order n ≥ k such that SWk(G) = w (or SWk(T) = w)? In this paper, we give some solutions to this problem.

3

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

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.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

2 Gutman I.

2 Li X.

2 Mao Y.

1 Bullington G.

1 Eroh L.

1 Gera R.

1 Winters S.

1 2018

1 2016

1 2011

The Steiner Wiener Index of A Graph

Inverse Problem on the Steiner Wiener Index

Closed k-stop distance in graphs