The asymptotic connectivity of labelled coloured regular bipartite graphs
The asymptotic connectivity of labelled coloured regular bipartite graphs
复制标题
带标签的彩色正则二分图的渐近连通性
DOI：
10.1007/bfb0071518
复制
发表时间：
1983
影响因子：
4.7
通讯作者：
M. Ellingham
中科院分区：
文献类型：
--
作者：
M. Ellingham
LCBG 的标记彩色二分图是一种二分（简单）图，其顶点为 2 色，并且每种颜色的顶点独立标记。结果表明，对于固定的 r⩾3，当 n → ∞ 时，r 连接的 2n 个顶点上的 r 正则 LCBG 的比例接近 1。另外，固定r⩾3且q>0；设 g=max(4,2{q/(2(r−2))})。那么以下类型的具有 2n 个顶点的 r-正则 LCBG 的数量渐近等于 n → ∞： 周长至少为 g 的；那些是循环 q 边连接的；以及那些循环 q 顶点连接的。
A labelled coloured bipartite graph, of LCBG, is a bipartite (simple) graph whose vertices have been 2-coloured and the vertices of each colour labelled independently. It is shown that for fixed r⩾3 the proportion of r-regular LCBGs on 2n vertices which are r-connected approaches 1 as n → ∞. Also, fix r⩾3 and q>0; let g=max(4,2{q/(2(r−2))}). Then the numbers of the following types of r-regular LCBGs with 2n vertices are asymptotically equal as n → ∞: those with girth at least g; those which are cyclically-q-edge-connected; and those which are cyclically-q-vertex-connected.