Graphs with large Steiner number

J. John; M. S. Malchijah Raj

doi:10.3842/umzh.v76i5.7409

J. John Department of Mathematics, Government College of Engineering, Tirunelveli, India
M. S. Malchijah Raj Department of Mathematics, Saveetha School of Engineering, Saveetha Institute of Medical and Technical Sciences, Saveetha University, Chennai, Tamil Nadu, India

DOI: https://doi.org/10.3842/umzh.v76i5.7409

Keywords: Steiner distance, Steiner set, Steiner number

Abstract

UDC 519.1

In 2002, Gary Chartrand and Ping Zhang [The Steiner number of a graph, Discrete Math., 242, 41--54 (2002)] characterized the connected graphs $G$ of order $p \geq 3$ with Steiner number $p$, $p-1,$ or $2.$ In our paper, we characterize all connected graphs $G$ of order $p \geq 4$ with Steiner number $s(G)=p-2$. In addition, we obtain some sharp Nordhaus–Gaddum bounds for the Steiner number of connected graphs whose complement is also connected.

References

F. Buckley, F. Harary, Distance in graphs, Addison-Wesley, Redwood City, CA (1990).

G. Chartrand, L. Lesniak, Graphs and digraphs, Fourth ed., Chapman and Hall/CRC, Boca Raton, FL (2005).

G. Chartrand, P. Zhang, The Steiner number of a graph, Discrete Math., 242, 41–54 (2002).

G. Chartrand, F. Harary, P. Zhang, On the geodetic number of a graph, Networks, 39, 1–6 (2002).

M. Changat, A. K. Lakshmikuttyamma, J. Mathews, A note on 3-Steiner intervals and betweeness, Discrete Math., 311, № 22, 2601–2609 (2011).

G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou, Steiner distance in graphs, ?asopis pro p?sto?n? matematiky, 114, 399–410 (1989).

C. Hernando, T. Jiang, M. Mora, I. M. Pelayo, C. Seara, On the Steiner, geodetic and hull number of graphs, Discrete Math., 293, 139–154 (2005).

J. John, Comment on ``Analogies between the geodetic number and the Steiner number of some classes of graphs'', Filomatv37, № 2, 585–589 (2023).

J. John, The vertex Steiner number of a graph, Trans. Combin., 9, № 2, 115–124 (2020); DOI: 10.22108/ TOC.2020.116191.1628.

J. John, The total Steiner number of a graph, Discrete Math., Algorithms and Appl., 12, № 3 (2020); DOI: 10.1142/ S179383092050038X.

J. John, On the vertex monophonic, vertex geodetic and vertex Steiner numbers of graphs, Asian-Eur. J. Math., 14, № 10, Article 2150171 (2021); DOI: 10.1142/S1793557121501710. DOI: https://doi.org/10.1142/S1793557121501710

J. John, M. S. Malchijah Raj, On the complement connected Steiner number of a graph, Acta Math. Univ. Comenian., 90, № 4, 377–389 (2021).

J. John, M. S. Malchijah Raj, The upper restrained Steiner number of a graph, Discrete Math., Algorithms and Appl., 12, № 1 (2020); DOI:10.1142/S1793830920500044. DOI: https://doi.org/10.1142/S1793830920500044

K. M. Kathiresan, S. Arockiaraj, R. Gurusamy, K. Amutha, On the Steiner radial number of graphs, Int. Workshop Combin. Algorithms, 65–72 (2012).

I. M. Pelayo, Comment on ``The Steiner number of a graph'' by G. Chartrand and P. Zhang, Discrete Math., 280, 259–263 (2004).

A. P. Santhakumaran, J. John, The edge Steiner number of a graph, J. Discrete Math. Sci. and Cryptogr., 10, 677–696 (2007).

A. P. Santhakumaran, J. John, The upper Steiner number of a graph, Graph Theory Notes of New York, 59, 9–14 (2010).

A. P. Santhakumaran, J. John, The forcing Steiner number of a graph, Discuss. Math. Graph Theory, 31, 171–181 (2011).

A. P. Santhakumaran, J. John, The forcing geodetic and the forcing Steiner numbers of a graph, Discuss. Math. Graph Theory, 31, 611–624 (2011).

I. G. Yero, J. A. Rodriguez-Velazquez, Analogies between the geodetic number and the Steiner number of some classes of graphs, Filomat, 29, № 8, 1781–1788 (2015).