DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(1) (2000) 129-138
DOI: 10.7151/dmgt.1112

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.

Received 27 September 1999
Revised 26 January 2000