# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## GEODETIC SETS IN GRAPHS

 Gary Chartrand Department of Mathematics and Statistics Western Michigan University, Kalamazoo, MI 49008, USA Frank Harary Department of Computer Science New Mexico State University, Las Cruces, NM 88003, USA Ping Zhang Department of Mathematics and Statistics Western Michigan University, Kalamazoo, MI 49008, USA

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

Keywords: geodetic set, geodetic number, upper geodetic number.

AMS Subject Classification: 05C12.

## References

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