2020/02/21 by Lilian Markenzon, Markenzon, Lilian, Christina F. E. M. Waga +1
Computer Science · Mathematics · #05C75 (Primary) 05C40 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2002.09244
openalex publication_date 2020/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study the toughness of Random Apollonian Networks (RANs), a random graph model which generates planar graphs with power-law properties. We consider their important characteristics: every RAN is a uniquely representable chordal graph and a planar 3-tree and as so, known results about these classes can be particularized. We establish a partition of the class in eight nontrivial subclasses and for each one of these subclasses we provide bounds for the toughness of their elements. We also study the hamiltonicity of the elements of these subclasses.