Geodetic number of random graphs of diameter 2

Gab Byung Chae, Edgar M. Palmer, Wai Cheong Siu

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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 languageEnglish
Pages (from-to)11-20
Number of pages10
JournalAustralasian Journal of Combinatorics
Publication statusPublished - 2002
Externally publishedYes


Dive into the research topics of 'Geodetic number of random graphs of diameter 2'. Together they form a unique fingerprint.

Cite this