# Geodetic sets in graphs

• Volume: 20, Issue: 1, page 129-138
• ISSN: 2083-5892

top

## Abstract

top
For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in 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. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u,v ∈ S, there exists a third vertex w of G that lies in some u-v geodesic but in no x-y geodesic for x, y ∈ S and {x,y} ≠ {u,v}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g⁺(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b+2.

## How to cite

top

Gary Chartrand, Frank Harary, and Ping Zhang. "Geodetic sets in graphs." Discussiones Mathematicae Graph Theory 20.1 (2000): 129-138. <http://eudml.org/doc/270425>.

@article{GaryChartrand2000,
abstract = {For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in 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. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u,v ∈ S, there exists a third vertex w of G that lies in some u-v geodesic but in no x-y geodesic for x, y ∈ S and \{x,y\} ≠ \{u,v\}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g⁺(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b+2.},
author = {Gary Chartrand, Frank Harary, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {geodetic set; geodetic number; upper geodetic number; distance; diameter},
language = {eng},
number = {1},
pages = {129-138},
title = {Geodetic sets in graphs},
url = {http://eudml.org/doc/270425},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Gary Chartrand
AU - Frank Harary
AU - Ping Zhang
TI - Geodetic sets in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 129
EP - 138
AB - For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in 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. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u,v ∈ S, there exists a third vertex w of G that lies in some u-v geodesic but in no x-y geodesic for x, y ∈ S and {x,y} ≠ {u,v}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g⁺(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b+2.
LA - eng
KW - geodetic set; geodetic number; upper geodetic number; distance; diameter
UR - http://eudml.org/doc/270425
ER -

## References

top
1. [1] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks (to appear). Zbl0987.05047
2. [2] G. Chartrand and L. Lesniak, Graphs & Digraphs (third edition, Chapman & Hall, New York, 1996).
3. [3] G. Chartrand and P. Zhang, The forcing geodetic number of a graph, Discuss. Math. Graph Theory 19 (1999) 45-58, doi: 10.7151/dmgt.1084. Zbl0927.05025
4. [4] G. Chartrand and P. Zhang, The geodetic number of an oriented graph, European J. Combin. 21 (2000) 181-189, doi: 10.1006/eujc.1999.0301. Zbl0941.05033
5. [5] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
6. [6] H.M. Mulder, The Interval Function of a Graph (Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
7. [7] L. Nebeský, A characterization of the interval function of a connected graph, Czech. Math. J. 44 (119) (1994) 173-178. Zbl0808.05046
8. [8] L. Nebeský, Characterizing of the interval function of a connected graph, Math. Bohem. 123 (1998) 137-144. Zbl0937.05036

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.