Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 11-20 |
| Number of pages | 10 |
| Journal | Australasian Journal of Combinatorics |
| Volume | 26 |
| Publication status | Published - 2002 |
| Externally published | Yes |