Geodesic
Maximal planar subgraphs of fixed girth in random graphs
Manuel Fernández1 ; Nicholas Sieger2 ; Michael Tait2
1School of Computer Science, Carnegie Mellon University
2Department of Mathematical Sciences, Carnegie Mellon University
The electronic journal of combinatorics, Tome 25 (2018) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 subgraph and for $G_{n,p}$ to contain a maximal planar subgraph of fixed girth $g$.
DOI : 10.37236/7114
Classification : 05C80, 05C60, 05C35
Mots-clés : planar subgraph, random graph, threshold

Manuel Fernández  1   ; Nicholas Sieger  2   ; Michael Tait  2

1 School of Computer Science, Carnegie Mellon University
2 Department of Mathematical Sciences, Carnegie Mellon University 
@article{10_37236_7114,
     author = {Manuel Fern\'andez and Nicholas Sieger and Michael Tait},
     title = {Maximal planar subgraphs of fixed girth in random graphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7114},
     zbl = {1388.05165},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7114/}
}
TY  - JOUR
AU  - Manuel Fernández
AU  - Nicholas Sieger
AU  - Michael Tait
TI  - Maximal planar subgraphs of fixed girth in random graphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7114/
DO  - 10.37236/7114
ID  - 10_37236_7114
ER  - 
%0 Journal Article
%A Manuel Fernández
%A Nicholas Sieger
%A Michael Tait
%T Maximal planar subgraphs of fixed girth in random graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7114/
%R 10.37236/7114
%F 10_37236_7114
Manuel Fernández; Nicholas Sieger; Michael Tait. Maximal planar subgraphs of fixed girth in random graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7114

Cité par Sources :