# Geodetic sets in graphs

Gary Chartrand; Frank Harary; Ping Zhang

Discussiones Mathematicae Graph Theory (2000)

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

## Access Full Article

top## Abstract

top## How to cite

topGary 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] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks (to appear). Zbl0987.05047
- [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. Zbl0927.05025
- [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] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
- [6] H.M. Mulder, The Interval Function of a Graph (Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
- [7] L. Nebeský, A characterization of the interval function of a connected graph, Czech. Math. J. 44 (119) (1994) 173-178. Zbl0808.05046
- [8] L. Nebeský, Characterizing of the interval function of a connected graph, Math. Bohem. 123 (1998) 137-144. Zbl0937.05036

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.