---

Discontinuity, Nonlinearity, and Complexity 10(3) (2021) 571--584 | DOI:10.5890/DNC.2021.09.015

He Li$^1$, Shumin Zhang$^2$, Bo Zhu$^2$, Chengfu Ye$^2$

$^1$ Department of Computer, Qinghai Normal University, Xining, Qinghai 810008, China

$^2$ Department of Mathematical Sciences, Qinghai Normal University, Xining, Qinghai 810008, China

Download Full Text PDF

 

Abstract

The Steiner $k$-diameter $sdiam_k(G)$ of a graph $G$, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical diameter. When $k=2$, $sdiam_2(G)=diam(G)$ is the classical diameter. Let $d,\ell$ and $n$ be natural numbers and $d

Acknowledgments

Supported by the NSFC No.11661068; NSFC No.11801296 NSFQH No.2019-ZJ-921; NSFQH No.2017-ZJ-949Q.

References

1. [1]	Bondy, J.A. and Murty, U.S.R. (2008), { Graph Theory}, GTM 244, Springer.

2. [2]	Goddard, W. and Oellrmann, O.R. (2011), Distance in graphs, in: M. Dehmer (Ed.) Structural Analysis of Complex Networks, Birkh\"{a}user, Dordrecht, 49--72.

3. [3]	Chung, F.R.K. (1987), Diameter of graphs: Old problems and new results, { 18th Southeastern Conf. on Combinatorics, Graph Theory and Computing}.

4. [4]	Du, D.Z., Lyuu, Y.D., and Hsu, D.F. (1994), Line digraph iteration and connectivity analysis of de Bruijn and Kautz graphs, { IEEE Trans. Comput.}, 42(5), 612--616.

5. [5]	Hsu, D.F. (1994), On container width and length in graphs, groups, and networks, { IEICE Transaction on Fundamentals of Electronics, Communications and Computer Science}, E77-A, 668--680.

6. [6]	Hsu, D.F. and {\L}uczak, T. (1994), Note on the $k$-diameter of $k$-regular $k$-connected graphs, { Discrete Math.} 133(1-3), 291--296.

7. [7]	Meyer, F.J. and Pradhan, D.K. (1987), Flip trees, { IEEE Trans. Computers} 37(3), 472--478.

8. [8]	Hakimi, S.L. (1971), Steiner's problem in graph and its implications { Networks}, 1(2), 113--133.

9. [9]	Levi, A.Y. (1971) Algorithm for shortest connection of a group of graph vertices, { Sov. Math. Dokl.}, 12, 1477--1481.

10. [10]	Hwang, F.K., Richards, D.S., and Winter, P. (1992), The Steiner Tree Problem, North-Holland, Amsterdam.

11. [11]	Garey, M.R. and Johnson, D.S. (1979), Computers and Intractibility: A Guide to the Theory of NP-Completeness, { IEEE Trans. Computers}, Freeman $\&$ Company, New York.

12. [12]	Bollob{a}s, B. (1978), { Extremal Graph Theory}, Acdemic press.

13. [13]	Homenko, N.P. and Ostroverhii, N.A. (1970), Diameter-critical graphs (in Russian), { Ukrainian Math. J.}, 22, 637--646.

14. [14]	Homenko, N.P. and Strok, V.V. (1971), Some combinatorial indentities for sums of composition coefficient (in Russian), { Ukrainian Math. J.}, 23, 830--837.

15. [15]	Ore, O. (1968), Diameter in graphs, { J. Combin. Theory}, 5, 75--81.

16. [16]	Watkins, M.E. (1976), A lower bound for the number of vertices of a graph, { Amer. Math. Monthly}, 74, 297.

17. [17]	Erd\"{o}s, P. and R{e}nyi, A. (1962), On a problem in the theory of graphs (in Hungarian), { Publ. Math. Inst. Hungar. Acad. Sci.}, 7.

18. [18]	Bollob{a}s, B. (1971), Graphs with a given diameter and maximal valency and with a minimal number of edges, in: ``Combinatorial Mathematics and its Applications'' (Welsh, D.J.A., ed.) { Academic Press} London and New York), 25--37.

19. [19]	Erd\"{o}s, P., R{e}nyi, A., and S{o}s, V.T. (1966), On a problem of graph theory, { Studia Sci. Math. Hungar.}, 1, 215--235.

20. [20]	Dankelmann, P., Swart, H., and Oellermann, O.R. (1999), Bounds on the Steiner diameter of a graph, { Combinatorics, Graph Theory, and Algorithms, Vol. I, II, New Issues Press}, Kalamazoo, MI.

21. [21]	Ali, P., Dankelmann, P., and Mukwembi, S. (2012), Upper bounds on the Steiner diameter of a graph, { Discrete Appl. Math.}, 160(12), 1845--1850.

22. [22]	Mao, Y.P. (2017), {The Steiner $3$-diameter of a graph}, ph {Bull. Iran. Math. Soc.}, 43(2), 439-454

23. [23]	Chartrand, G., Oellermann, O.R., Tian, S., and Zou, H.B. (1989), Steiner distance in graphs, { {C}asopis pro p\v{e}stov{a}n{i} matematiky}, 114, 399--410.

24. [24]	Wang, Z., Mao, Y.P., and Li, H.Z. (2018), ph{On the Steiner $4$-Diameter of graph}, Journal of Interconnection Networks, 18(1), 1850002.

25. [25]	Ali, P. (2013), The Steiner diameter of a graph with prescribed girth, { Discrete Math.}, 313(12), 1322--1326.

26. [26]	Bloom, G.S. (1988), A characterization of graphs of diameter two, { Amer. Math. Monthly}, 95(1), 37--38.

27. [27]	Buckley, F. and Harary, F. (1990), Distance in Graphs, { Addision-Wesley}, Redwood City, CA.

28. [28]	C{a}ceresa, J., M{a}rquezb, A., and Puertasa, M.L. (2008), Steiner distance and convexity in graphs, { European J. Combin.}, 29(3), 726--736.

29. [29]	Chartrand, G., Okamoto, F., and Zhang, P. (2010), Rainbow Trees in Graphs and Generalized Connectivity, { Networks}, 55(4), 360--367.

30. [30]	Dankelmann, P., Swart, H.C., and Oellermann, O.R. (2008), On the average Steiner distance of graphs with prescribed properties, { Discrete Appl. Math.}, 79(1-3), 91--103.

31. [31]	Day, D.P., Oellermann, O.R., and Swart, H.C. (1994), Steiner Distance-Hereditary Graphs, { SIAM J. Discrete Math.}, 7(3), 437--442.

32. [32]	D'Atri, A. and Moscarini, M. (1988), Distance-Hereditary Graphs, Steiner Trees, and Connected Domination, { SIAM J. Comput.}, 17(3), 521--538.

33. [33]	Meyer, F.J. and Pradhan, D.K. (1987), Flip trees, { IEEE Trans. Computers}, 37(3), 472--478.

34. [34]	Goddard, W., Oellrmann, O.R., and Swart, H.C. (1994), Steiner distance stable graphs, { Discrete Math.}, 132(1-3), 65--73.

35. [35]	Mao, Y. The Steiner diameter of a graph, accepted by { Bull. Iran. Math. Soc.}