Inverse Problem on the Steiner Wiener Index

• Autorzy: Xueliang Li , Yaping Mao , Ivan Gutman
• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

distance; Steiner distance; Wiener index; Steiner Wiener index

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C05: Trees
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 83-95

Daty

wydano

2018-02-01

otrzymano

2015-09-16

poprawiono

2016-10-05

zaakceptowano

2016-10-05

online

2017-12-30

Twórcy

autor

Xueliang Li

• , , ,

autor

Yaping Mao

• , , Qinghai ,

autor

Ivan Gutman

• Faculty of Science P.O. Box 60, , , and , ,

Identyfikatory

DOI

10.7151/dmgt.2000