PDF

Discussiones Mathematicae Graph Theory 19(1) (1999) 45-58
DOI: https://doi.org/10.7151/dmgt.1084

THE FORCING GEODETIC NUMBER OF A GRAPH

Gary Chartrand and Ping Zhang

Department of Mathematics and Statistics
Western Michigan University, Kalamazoo, MI 49008, USA

Dedicated to Frank Harary
on the occasion of the 50th anniversary of his Ph.D.

Abstract

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)}.

Keywords: geodetic set, geodetic number, forcing geodetic number.

1991 Mathematics Subject Classification: 05C12.

References

[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).

Received 15 April 1998
Revised 11 January 1999