For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic number $f_G(S)$ of S is the minimum cardinality among the forcing subsets of S, and the forcing geodetic number f(G) of G is the minimum forcing geodetic number among all minimum geodetic sets of G. The forcing geodetic numbers of several classes of graphs are determined. For every graph G, f(G) ≤ g(G). It is shown that for all integers a, b with 0 ≤ a ≤ b, a connected graph G such that f(G) = a and g(G) = b exists if and only if (a,b) ∉ {(1,1),(2,2)}.
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.
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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.