# The forcing geodetic number of a graph

• Volume: 19, Issue: 1, page 45-58
• ISSN: 2083-5892

top

## Abstract

top
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}\left(S\right)$ 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).

## How to cite

top

Gary Chartrand, and Ping Zhang. "The forcing geodetic number of a graph." Discussiones Mathematicae Graph Theory 19.1 (1999): 45-58. <http://eudml.org/doc/270610>.

@article{GaryChartrand1999,
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).},
author = {Gary Chartrand, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {geodetic set; geodetic number; forcing geodetic number; geodetic closure; shortest paths},
language = {eng},
number = {1},
pages = {45-58},
title = {The forcing geodetic number of a graph},
url = {http://eudml.org/doc/270610},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Gary Chartrand
AU - Ping Zhang
TI - The forcing geodetic number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 1
SP - 45
EP - 58
AB - 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).
LA - eng
KW - geodetic set; geodetic number; forcing geodetic number; geodetic closure; shortest paths
UR - http://eudml.org/doc/270610
ER -

## References

top
1. [1] G. Chartrand, F. Harary and P. Zhang, The geodetic number of a graph, Networks (to appear). Zbl0987.05047
2. [2] G. Chartrand, F. Harary, and P. Zhang, On the hull number of a graph, Ars Combin. (to appear). Zbl1064.05049

top

## 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.