Maximal Planar Subgraphs of Fixed Girth in Random Graphs

Electronic Journal Of Combinatorics

Manuel Fernández¹ 

关键词: Planar subgraph;    Random graph;    Threshold;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

In 1991, Bollobás and Frieze showed that the threshold for $G_{n,p}$ to contain a spanning maximal planar subgraph is very close to $p = n^{-1/3}$. In this paper, we compute similar threshold ranges for $G_{n,p}$ to contain a maximal bipartite planar subg

【 授权许可】

Others