PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 19 | 1 | 45-58
Tytuł artykułu

The forcing geodetic number of a graph

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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)}.
Kategorie tematyczne
Wydawca
Rocznik
Tom
19
Numer
1
Strony
45-58
Opis fizyczny
Daty
wydano
1999
otrzymano
1998-04-15
poprawiono
1999-01-11
Twórcy
  • Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA
autor
  • Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA
Bibliografia
  • [1] G. Chartrand, F. Harary and P. Zhang, The geodetic number of a graph, Networks (to appear).
  • [2] G. Chartrand, F. Harary, and P. Zhang, On the hull number of a graph, Ars Combin. (to appear).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1084
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ć.