Steiner $4$-Diameter, Maximum Degree and Size of a Graph
DOI:
https://doi.org/10.5890/DNC.2021.09.015Abstract
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\lt n$, $\ell\lt n$. Denote by $\mathscr{H}_k(n,\ell,d)$ the set of all graphs of order $n$ with maximum degree $\ell$ and $sdiam_k(G)\leq d$. Let $e_k(n,\ell,d)=\min\{e(G):G\in \mathscr{H}_k(n,\ell,d)\}$. In this paper, we focus on the case $k=4$, and study the exact value of $e_4(n,\ell,d)$.References
[1] Bondy, J.A. and Murty, U.S.R. (2008), { Graph Theory}, GTM 244, Springer.
[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] Chung, F.R.K. (1987), Diameter of graphs: Old problems and new results, { 18th Southeastern Conf. on Combinatorics, Graph Theory and Computing}.
[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] 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] 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] Meyer, F.J. and Pradhan, D.K. (1987), Flip trees, { IEEE Trans. Computers} 37(3), 472--478.
[8] Hakimi, S.L. (1971), Steiner's problem in graph and its implications { Networks}, 1(2), 113--133.
[9] Levi, A.Y. (1971) Algorithm for shortest connection of a group of graph vertices, { Sov. Math. Dokl.}, 12, 1477--1481.
[10] Hwang, F.K., Richards, D.S., and Winter, P. (1992), The Steiner Tree Problem, North-Holland, Amsterdam.
[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] Bollob{a}s, B. (1978), { Extremal Graph Theory}, Acdemic press.
[13] Homenko, N.P. and Ostroverhii, N.A. (1970), Diameter-critical graphs (in Russian), { Ukrainian Math. J.}, 22, 637--646.
[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] Ore, O. (1968), Diameter in graphs, { J. Combin. Theory}, 5, 75--81.
[16] Watkins, M.E. (1976), A lower bound for the number of vertices of a graph, { Amer. Math. Monthly}, 74, 297.
[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] 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] 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] 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] 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] Mao, Y.P. (2017), {The Steiner $3$-diameter of a graph}, ph {Bull. Iran. Math. Soc.}, 43(2), 439-454
[23] Chartrand, G., Oellermann, O.R., Tian, S., and Zou, H.B. (1989), Steiner distance in graphs, { {C}asopis pro pv{e}stov{a}n{i} matematiky}, 114, 399--410.
[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] Ali, P. (2013), The Steiner diameter of a graph with prescribed girth, { Discrete Math.}, 313(12), 1322--1326.
[26] Bloom, G.S. (1988), A characterization of graphs of diameter two, { Amer. Math. Monthly}, 95(1), 37--38.
[27] Buckley, F. and Harary, F. (1990), Distance in Graphs, { Addision-Wesley}, Redwood City, CA.
[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] Chartrand, G., Okamoto, F., and Zhang, P. (2010), Rainbow Trees in Graphs and Generalized Connectivity, { Networks}, 55(4), 360--367.
[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] Day, D.P., Oellermann, O.R., and Swart, H.C. (1994), Steiner Distance-Hereditary Graphs, { SIAM J. Discrete Math.}, 7(3), 437--442.
[32] D'Atri, A. and Moscarini, M. (1988), Distance-Hereditary Graphs, Steiner Trees, and Connected Domination, { SIAM J. Comput.}, 17(3), 521--538.
[33] Meyer, F.J. and Pradhan, D.K. (1987), Flip trees, { IEEE Trans. Computers}, 37(3), 472--478.
[34] Goddard, W., Oellrmann, O.R., and Swart, H.C. (1994), Steiner distance stable graphs, { Discrete Math.}, 132(1-3), 65--73.
[35] Mao, Y. The Steiner diameter of a graph, accepted by { Bull. Iran. Math. Soc.}
Article Metrics
Usage tracking begins September 1, 2026.