Upper bounds on the Steiner diameter of a graph
Upper bounds on the Steiner diameter of a graph
复制标题
DOI：
10.1016/j.dam.2012.03.031
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
P. Ali;P. Dankelmann;S. Mukwembi
中科院分区：
文献类型：
--
作者：
P. Ali;P. Dankelmann;S. Mukwembi
设G是p阶连通图，S是G的非空顶点集.则S的Steiner距离d（S）是G的顶点集包含S的连通子图的最小尺寸。若n是整数，2≤n≤p，则G的Steiner n-直径diamn（G）是G的任意n-顶点子集的最大Steiner距离.利用图G的阶和最小度给出了图G的diamn（G）的一个界。我们的结果意味着一个束缚的普通直径的Erdensys，Pach，Pollack和Tuza。本文给出了无K_3图和无C_4图的diamn（G）的改进界。此外，我们构造图，以表明边界是渐近最好的可能。
Let G be a connected graph of order p and S a nonempty set of vertices of G. Then the Steiner distance d(S) of S is the minimum size of a connected subgraph of G whose vertex set contains S. If n is an integer, 2≤n≤p, the Steiner n-diameter, diamn(G), of G is the maximum Steiner distance of any n-subset of vertices of G. We give a bound on diamn(G) for a graph G in terms of the order of G and the minimum degree of G. Our result implies a bound on the ordinary diameter by Erdős, Pach, Pollack and Tuza. We obtain improved bounds on diamn(G) for K3-free graphs and C4-free graphs. Moreover, we construct graphs to show that the bounds are asymptotically best possible.