Geodetic number of random graphs of diameter 2.
Gab-Byung Chae, Edgar M. Palmer, Wai-Cheong Siu · 2002
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ös 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 agivengraphG. Our technique can be applied to other random graphs of diameter 2 and to random digraphs. 1