Planarity and genus of sparse random bipartite graphs
The genus of the binomial random graph G(n,p) is well understood for a wide range of
p=p(n). Recently, the study of the genus of the random bipartite graph G(n_1,n_2,p), with
partition classes of size n_1 and n_2, was initiated by Mohar and Jing, who showed that
when n_1 and n_2 are comparable in size and p=p(n_1,n_2) is significantly larger than
(n_1n_2)^-12 the genus of the random bipartite graph has a similar behavior to that of the
binomial random graph. In this paper we show that there is a threshold for planarity of the …
p=p(n). Recently, the study of the genus of the random bipartite graph G(n_1,n_2,p), with
partition classes of size n_1 and n_2, was initiated by Mohar and Jing, who showed that
when n_1 and n_2 are comparable in size and p=p(n_1,n_2) is significantly larger than
(n_1n_2)^-12 the genus of the random bipartite graph has a similar behavior to that of the
binomial random graph. In this paper we show that there is a threshold for planarity of the …
The genus of the binomial random graph is well understood for a wide range of . Recently, the study of the genus of the random bipartite graph , with partition classes of size and , was initiated by Mohar and Jing, who showed that when and are comparable in size and is significantly larger than the genus of the random bipartite graph has a similar behavior to that of the binomial random graph. In this paper we show that there is a threshold for planarity of the random bipartite graph at and investigate the genus close to this threshold, extending the results of Mohar and Jing. It turns out that there is qualitatively different behavior in the case where and are comparable, when with high probability (whp) the genus is linear in the number of edges, than in the case where is asymptotically smaller than , when whp the genus behaves like the genus of a sparse random graph for an appropriately chosen .
Society for Industrial and Applied Mathematics以上显示的是最相近的搜索结果。 查看全部搜索结果