Geodesic
Geodetic sets in graphs
Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 129-138.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: geodetic set, geodetic number, upper geodetic number 
@article{DMGT_2000_20_1_a9,
     author = {Chartrand, Gary and Harary, Frank and Zhang, Ping},
     title = {Geodetic sets in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {129--138},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2000},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a9/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Harary, Frank
AU  - Zhang, Ping
TI  - Geodetic sets in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2000
SP  - 129
EP  - 138
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a9/
LA  - en
ID  - DMGT_2000_20_1_a9
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Harary, Frank
%A Zhang, Ping
%T Geodetic sets in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2000
%P 129-138
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a9/
%G en
%F DMGT_2000_20_1_a9
Chartrand, Gary; Harary, Frank; Zhang, Ping. Geodetic sets in graphs. Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 129-138. http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a9/

[1] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks (to appear).

[2] G. Chartrand and L. Lesniak, Graphs Digraphs (third edition, Chapman Hall, New York, 1996).

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

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

[5] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).

[6] H.M. Mulder, The Interval Function of a Graph (Mathematisch Centrum, Amsterdam, 1980).

[7] L. Nebeský, A characterization of the interval function of a connected graph, Czech. Math. J. 44 (119) (1994) 173-178.

[8] L. Nebeský, Characterizing of the interval function of a connected graph, Math. Bohem. 123 (1998) 137-144.