Geodetic number of random graphs of diameter 2

Buckley and Harary introduced several graphical invariants related to convexity theory, such as the geodetic number of a graph. These invariants have been the subject of much study and their determination has been shown to be NP-hard. We use the probabilistic method developed by Erd̈os to determine the asymptotic behavior of the geodetic number of random graphs with fixed edge probability. As a consequence we have a random greedy algorithm for a good approximation of a geodetic basis of a given graph G. Our technique can be applied to other random graphs of diameter 2 and to random digraphs.