On the forcing geodetic and forcing steiner numbers of a graph

A.P. Santhakumaran; J. John

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 611-624
  • 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. The geodetic number g(G) and the forcing geodetic number f(G) of a graph G are defined in [2]. It is proved in [6] that there is no relationship between the geodetic number and the Steiner number of a graph so that there is no relationship between the forcing geodetic number and the forcing Steiner number of a graph. We give realization results for various possibilities of these four parameters.

How to cite

top

A.P. Santhakumaran, and J. John. "On the forcing geodetic and forcing steiner numbers of a graph." Discussiones Mathematicae Graph Theory 31.4 (2011): 611-624. <http://eudml.org/doc/271013>.

@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. The geodetic number g(G) and the forcing geodetic number f(G) of a graph G are defined in [2]. It is proved in [6] that there is no relationship between the geodetic number and the Steiner number of a graph so that there is no relationship between the forcing geodetic number and the forcing Steiner number of a graph. We give realization results for various possibilities of these four parameters.},
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 = {4},
pages = {611-624},
title = {On the forcing geodetic and forcing steiner numbers of a graph},
url = {http://eudml.org/doc/271013},
volume = {31},
year = {2011},
}

TY - JOUR
AU - A.P. Santhakumaran
AU - J. John
TI - On the forcing geodetic and forcing steiner numbers of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 611
EP - 624
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. The geodetic number g(G) and the forcing geodetic number f(G) of a graph G are defined in [2]. It is proved in [6] that there is no relationship between the geodetic number and the Steiner number of a graph so that there is no relationship between the forcing geodetic number and the forcing Steiner number of a graph. We give realization results for various possibilities of these four parameters.
LA - eng
KW - geodetic number; Steiner number; forcing geodetic number; forcing Steiner number
UR - http://eudml.org/doc/271013
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, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1-6, doi: 10.1002/net.10007. Zbl0987.05047
  4. [4] G. Chartrand and P. Zhang, The Steiner number of a graph, Discrete Math. 242 (2002) 41-54, doi: 10.1016/S0012-365X(00)00456-8. Zbl0988.05034
  5. [5] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling 17 (1993) 89-95, doi: 10.1016/0895-7177(93)90259-2. Zbl0825.68490
  6. [6] I.M. Pelayo, Comment on 'The Steiner number of a graph' by G. Chartrand and P. Zhang, Discrete Math. 242 (2002) 41-54. 
  7. [7] A.P. Santhakumaran, P. Titus and J. John, On the connected geodetic number of a graph, J. Combin. Math. Combin. Comput. 69 (2009) 219-229. Zbl1200.05073
  8. [8] A.P. Santhakumaran, P. Titus and J. John, The upper connected geodetic number and forcing connected geodetic number of a graph, Discrete Appl. Math. 159 (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.