×

On the forcing geodetic and forcing steiner numbers of a graph. (English) Zbl 1255.05070

Summary: For a connected graph \(G = (V,E)\), a set \(W \subseteq 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 \subseteq 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_{s}(W)\), is the cardinality of a minimum forcing subset of \(W\). The forcing Steiner number of \(G\), denoted by \(f_{s}(G\)), is \( f_{s}(G)\) = min\(\{f_{s}(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 [G. Chartrand and P. Zhang, Discuss. Math., Graph Theory 19, No. 1, 45–58 (1999; Zbl 0927.05025)].
It is proved in [G. Chartrand and P. Zhang, Discrete Math. 242, No. 1–3, 41–54 (2002; Zbl 0988.05034)] 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.

MSC:

05C12 Distance in graphs
05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI