In this work, we analyze fundamental properties of Random Apollonian Networks, a popular random graph model which generates planar graphs with power law properties. Specifically, we analyze the following properties:
- the degree distribution,
- the largest degrees, the largest eigenvalues ( is a constant),
- the diameter.
Random regular graphs. An edge colored graph is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph , denoted by , is the smallest number of colors that are needed in order to make rainbow connected. In this work we study the rainbow connection of the random -regular graph of order~, where is a constant. We prove that with probability tending to one as goes to infinity the rainbow connection of satisfies , which is best possible up to a hidden constant.
Note: The optimal result for 3-regular random graphs was proved by Michael Molloy.
Random Erdős–Rényi graphs. We prove optimal results for rainbow connectivity at the connectivity threshold.
- Rainbow connectivity of sparse random graphs, by Andrzej Dudek, Alan Frieze, Charalampos E. Tsourakakis
- Rainbow Connectivity of Sparse Random Graphs, Alan Frieze, Charalampos E. Tsourakakis
In our work “Scalable motif-aware community detection” we introduce the concept of triangle expanders, that serves as the theoretical basis of the theory behind motif based clustering.