The vertex Steiner number of a graph

Document Type : Research Paper

Author

Department of Mathematics, Government college of Engineering, Tirunelveli, India- 627007

Abstract

‎Let $x$ be a vertex of a connected graph $G$ and $W \subset V(G)$ such that $x\notin W$‎. ‎Then $W$ is called an $x$-Steiner set of G if $W \cup \lbrace x \rbrace$ is a Steiner set of G‎. ‎The minimum cardinality of an $x$-Steiner set of G is defined as $x$-Steiner number of G and denoted by $s_x(G)$‎. ‎Some general properties satisfied by these concepts are studied‎. ‎The $x$-Steiner numbers of certain classes of graphs are determined‎. ‎Connected graphs of order p with $x$-Steiner number 1 or $p-1$ are characterized‎. ‎It is shown that for every pair a, ‎b of integers with $2 \leq a \leq b$‎, ‎there exists a connected graph G such that $s(G)} = a$ and $s_{x}(G)=b$ for some vertex $x$ in G‎, ‎where $s(G)$ is the Steiner number of a graph‎.

Keywords

Main Subjects

References

[1] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley Publishing Company, Advanced Book Program,
Redwood City, CA, 1990.
[2] B. Bresar and M. Changat, Steiner intervals, geodesic intervals, betweenness, Discrete Math., 309 (2009) 6114–
6125.
[3] G. Chartrand, O. R. Oellermann, S. L.Tian and H. L. Zou, Steiner distance in graphs, C̆asopis Pĕst. Mat., 114
(1989) 399–410.
[4] G. Chartrand and P. Zhang, The Steiner number of a graph, Discrete Math., 242, (2002) 41–54.
[5] R. Eballe, S. Canoy, Jr., Steiner sets in the join and composition of graphs, Congr. Numer., 170 (2004) 65–73.
[6] M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness,
Freeman Company, New York, 1979.
[7] S. L. Hakimi, Steiner’s problem in graph and its implications, Networks, 1 (1971) 113–133.
[8] F. K. Hwang, D. S. Richards and P. Winter, Annals of Discrete Mathematics, 53, North-Holland Publishing Co.,
Amsterdam, 1992.
[9] C. Hernando, T. Jiang, M. Mora, I. M. Pelayo and C. Seara, On the Steiner, geodetic and hull number of graphs,
Discrete Math., 293 (2005) 139–154.
[10] J. John, G. Edwin and P. Arul Paul Sudhahar, The Steiner domination number of a graph, International Journal
of Mathematics and Computer Applications Research, 3 (2013) 37–42.
[11] J. John and M. S. Malchijah Raj, The upper restrained Steiner number of a graph, Discrete Math. Algorithms
Appl., 12 (2020) 2050004 (12 pages).
[12] J.John,ThetotalSteinernumberofagraph,DiscreteMath.AlgorithmsAppl.,(2020) DOI:10.1142/S179383092050038X.
[13] K. M. Kathiresan, S. Arockiaraj, R. Gurusamy and K. Amutha, On the Steiner radial number of graphs, Combi-
natorial algorithms, Lecture Notes in Comput. Sci., Springer, Heidelberg, 2012 65–72.
[14] A. Y. Levi, Algorithm for shortest connection of a group of graph vertices, Sov. Math. Dokl., 12 (1971) pp. 14.
[15] M. S. Malchijah Raj and J. John, The restrained edge Steiner number of a graph, Journal of Applied Science and
Computations, 4 (2019) 1–8.
[16] M. S. Malchijah Raj and J. John, The total restrained Steiner number of a graph, Journal of Advanced Research
in Dynamical and Control Systems, 10 (2018) 396–401.
[17] P. A. Ostrand, Graphs with specified radius and diameter, Discrete Math., 4 (1973) 71–75.
[18] I. M. Pelayo, Comment on “The Steiner number of a graph”, Discrete Math., 242 (2002) 41–54.
[19] A. P. Santhakumaran and J. John, The upper Steiner number of a graph, Graph Theory Notes N. Y., 59 (2010)
9–14.
[20] A. P. Santhakumaran and J. John, The forcing Steiner number of a graph, Discuss. Math. Graph Theory, 31
(2011) 171–181.
[21] A. P. Santhakumaran and J. John, On the forcing geodetic and forcing Steiner numbers of a graph, Discuss. Math.
Graph Theory, 31 (2011) 611–624.
[22] L. D. Tong, Geodetic sets and Steiner sets in graphs, Discrete Math., 309 (2009) 4205–4207.
[23] P. Winter, Steiner problems in networks: A survey, Networks, 17 (1987) 129–167.

Files

Cited by

History

  • Receive Date: 24 March 2019
  • Revise Date: 22 April 2020
  • Accept Date: 30 April 2020
  • Published Online: 01 June 2020

Share

How to cite

Statistics