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

Анотація

УДК 519.1

Графи з великим числом Штейнера

У 2002 році Гері Чартранд та Пінг Чжан [The Steiner number of a graph, Discrete Math., 242, 41–54 (2002)] охарактеризували зв'язні графи $G$ порядку $p \geq 3$ з числом Штейнера $p$, $p-1$ або $2.$ У цій статті охарактеризовано всі зв'язні графи $G$ порядку $p \geq 4$ з числом Штейнера $s(G)=p-2$. Також отримано деякі точні межі Нордгауза\,--\,Гаддума для числа Штейнера зв'язних графів, доповнення яких також є зв'язними.

Посилання

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).