The forcing steiner number of a graph

A.P. Santhakumaran; J. John

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 1, page 171-181
  • ISSN: 2083-5892

Abstract

top
For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The forcing Steiner number of W, denoted by fₛ(W), is the cardinality of a minimum forcing subset of W. The forcing Steiner number of G, denoted by fₛ(G), is fₛ(G) = min{fₛ(W)}, where the minimum is taken over all minimum Steiner sets W in G. Some general properties satisfied by this concept are studied. The forcing Steiner numbers of certain classes of graphs are determined. It is shown for every pair a, b of integers with 0 ≤ a < b, b ≥ 2, there exists a connected graph G such that fₛ(G) = a and s(G) = b.

How to cite

top

A.P. Santhakumaran, and J. John. "The forcing steiner number of a graph." Discussiones Mathematicae Graph Theory 31.1 (2011): 171-181. <http://eudml.org/doc/270960>.

@article{A2011,
abstract = {For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The forcing Steiner number of W, denoted by fₛ(W), is the cardinality of a minimum forcing subset of W. The forcing Steiner number of G, denoted by fₛ(G), is fₛ(G) = min\{fₛ(W)\}, where the minimum is taken over all minimum Steiner sets W in G. Some general properties satisfied by this concept are studied. The forcing Steiner numbers of certain classes of graphs are determined. It is shown for every pair a, b of integers with 0 ≤ a < b, b ≥ 2, there exists a connected graph G such that fₛ(G) = a and s(G) = b.},
author = {A.P. Santhakumaran, J. John},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {geodetic number; Steiner number; forcing geodetic number; forcing Steiner number},
language = {eng},
number = {1},
pages = {171-181},
title = {The forcing steiner number of a graph},
url = {http://eudml.org/doc/270960},
volume = {31},
year = {2011},
}

TY - JOUR
AU - A.P. Santhakumaran
AU - J. John
TI - The forcing steiner number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 1
SP - 171
EP - 181
AB - For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The forcing Steiner number of W, denoted by fₛ(W), is the cardinality of a minimum forcing subset of W. The forcing Steiner number of G, denoted by fₛ(G), is fₛ(G) = min{fₛ(W)}, where the minimum is taken over all minimum Steiner sets W in G. Some general properties satisfied by this concept are studied. The forcing Steiner numbers of certain classes of graphs are determined. It is shown for every pair a, b of integers with 0 ≤ a < b, b ≥ 2, there exists a connected graph G such that fₛ(G) = a and s(G) = b.
LA - eng
KW - geodetic number; Steiner number; forcing geodetic number; forcing Steiner number
UR - http://eudml.org/doc/270960
ER -

References

top
  1. [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, CA, 1990). Zbl0688.05017
  2. [2] G. Chartrand and P. Zhang, The forcing geodetic number of a graph, Discuss. Math. Graph Theory 19 (1999) 45-58, doi: 10.7151/dmgt.1084. Zbl0927.05025
  3. [3] G. Chartrand and P. Zhang, The forcing dimension of a graph, Mathematica Bohemica 126 (2001) 711-720. Zbl0995.05046
  4. [4] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1-6, doi: 10.1002/net.10007. Zbl0987.05047
  5. [5] G. Chartrand, F. Harary and P. Zhang, The Steiner Number of a Graph, Discrete Math. 242 (2002) 41-54. Zbl0988.05034
  6. [6] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modelling 17 (1993) 89-95, doi: 10.1016/0895-7177(93)90259-2. Zbl0825.68490
  7. [7] C. Hernando, T. Jiang, M. Mora, I.M. Pelayo and C. Seara, On the Steiner, geodetic and hull numbers of graphs, Discrete Math. 293 (2005) 139-154, doi: 10.1016/j.disc.2004.08.039. Zbl1062.05052
  8. [8] I.M. Pelayo, Comment on 'The Steiner number of a graph' by G. Chartrand and P. Zhang, Discrete Math. 242 (2002) 41-54. 
  9. [9] A.P. Santhakumaran, P. Titus and J. John, On the Connected Geodetic Number of a Graph, J. Combin. Math. Combin. Comput. 69 (2009) 205-218. Zbl1200.05073
  10. [10] A.P. Santhakumaran, P. Titus and J. John, The Upper Connected Geodetic Number and Forcing Connected Geodetic Number of a Graph, Discrete Appl. Math. 157 (2009) 1571-1580, doi: 10.1016/j.dam.2008.06.005. Zbl1175.05074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.