Some Topics On The Two Steiner Distance Parameters

Steiner distance problem is a classical combinatorial optimization problem,which is widely used in modern production and life.Let G be a connected graph of order at least 2 and let S be a nonempty set of vertices of G,then the Steiner distance ds(S)a-mong the vertices of S is the minimum size of a connected subgraphs whose vertex set contains S.Then the Steiner k-Wiener index SWk(G)and Steiner Harary k-index ofG is defined as SWk(G)=?S(?)V(G),|S|=k dG(S)and SHk(G)=?S(?)V(G),|S|=k1/dG(S).These two types of index are topological index,which defined on the basis of distance.In the field of chemistry,topological index of graph can reflect the structural charac-teristics and properties of molecules,which is more convenient for scholars to analyze and solve relevant problems.Let f(G)be an invariant of G,G is the completement graph of G,the Nordhaus-Gaddum problem is to determine sharp bounds of f(G)+f(G)and f(G)·f(G).In this paper,we study the Steiner k-Wiener index of trees with given diameter,and the Nordhaus-Gaddum type results of Steiner Harary k-index.The main results are as follows:Firstly,we study Steiner k-Wiener index of trees with diameter 3,4,n-2,the results are as follows:(1)SWk(Tn,3)=(n-2)(n-1 k-1)+(n k)-(a+2 k)-(n-a-2 k),(2)SWk(Tn,4)=(n-l-1)(n-1 k-1)+l(n k)-?i=1 l(ai+1 k)-?i=1 l(n-ai-1 k),(3)SWk(Ti)=(k-1)(n k+1)+(k-2)(n k)+(n-1 k-1)+i(n-1 k-1)-(k-1)(i k)+(n-i)(n-i-1 k-1)(k-1)(n-i k).Secondly,we obtain the upper and lower bounds of Nordhaus-Gaddum type re-sults of SHk(G)index,3?<k?n.In particular,we have shown that when k=n,n-1 and k=3,the bound on the result of SHk(G)Nordhaus-Gaddum type result is further strengthened.When k=n,the value of the sum and product of SHk(G)and SHk(G)is 2/n-1 and 1/(n-1)2.When k=n-1,if the graph satisfies the graph class depicted by Akiyama and Harary,we obtained the value or bound of Nordhaus-Gaddum type result of SHn-1(G).When k=3,restricted the order of the graph and the diameter of the graph or its complement graph,we improve these bounds of Nordhaus-Gaddum type result of SHk(G).That is,we obtain the sharp bounds of SH3(G)and SH3(G),and give example to show the bounds can be achieved.