北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 2018, Vol. 47(2): 175-188
 研究论文
 一类稀疏随机图的距离匹配数 On Distance Matching Number in a Class of Sparse Random Graphs 田方 TIAN Fang 海财经大学数学学院, 上海财经大学计算数学与金融大数据研究中心, 上海, 200433 School of Mathematics, Research Center of Computational Mathematics and Financial Big Data,Shanghai University of Finance and Economics, Shanghai, 200433, P. R. China 收稿日期: 2016-07-28 出版日期: 2018-05-16 2018, Vol. 47(2): 175-188 DOI: 10.11845/sxjz.2016100b
 PDF [199 KB] 47 下载 268 浏览 引用导出
0
/   /   推荐

Abstract：For any positive integer $k$, the distance matching number, denoted by $um_k(G)$,is the largest size of a collection of edges in $G$ such that no two edges are within distance $k$.Let $G_{n,p}$ stand for the classic Erd\H{o}s-Rènyi random graph. Kang and Manggala presented an upper bound of $um_k(G_{n,p})$ for $k\geq 2$ and $p=\frac{c}{n}$ with the constant $c$ sufficiently large. In this paper,we firstly consider the lower bound of $um_k(G_{n,p})=\Omega(\log n)$ for $k\geq 2$ by the second moment method in this class of sparse random graphs.
Key wordsdistance matching number    Erd\H{o}s-Rè    nyi random graph    second moment method
 PACS: O157.5
 [1] Cameron, K., Induced matchings, Discrete Appl. Math., 1989, 24(1/2/3): 97-102.[2] Kaiser, T. and Kang, R.J., The distance-$t$ chromatic index of graphs, Comb. Probab. Comput.,2014, 23(1): 90-101.[3] Kang, R.J. and Manggala, P., Distance edge-colorings and matchings, Discrete Appl. Math., 2012, 160: 2435-2439.[4]Maftouhi, A., The minimum size of a maximal strong matching in a random graph, Australas. J. Combin., 1995, 12: 77-80.[5] Maftouhi, A. and Gordones, L.M., The maximum order of a strong matching in a random graph, Australas. J. Combin., 1994, 10: 97-104.[6] Stockmeyer, L.J. and Vazirani, V.V., NP-completeness of some generalizations of the maximum matching problem,Inform. Process. Lett., 1982, 15(1): 14-19.[7] Mitzenmacher M. and Upfal U., Probability and Computing-randomized algorithms and probabilistic analysis, Cambridge Press, 2005.[8] Orlovich Y., Finke G., Gordon V. and Zverovich I., Approximability results for the maximum and minimum maximal induced matching problems, Discrete Optim., 2008, 5: 584-593.
 [1] 任秀秀,杨卫华. 几类特殊有向循环图的核[J]. 数学进展, 2019, 48(2): 137-144. [2] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155. [3] 石慧苓, 高云澍. 标准多重图中点不交的重边四边形[J]. 数学进展, 2018, 47(3): 348-362. [4] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372. [5] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382. [6] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681. [7] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354. [8] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12. [9] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54. [10] 冯荣权, 曾丽伟. 有向强正则图及其构造[J]. 数学进展, 2016, 45(6): 817-839. [11] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720. [12] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726. [13] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490. [14] 李晓艳，陈敏，王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499. [15] 姚京京, 邵泽玲, 徐常青. \mbox{\boldmath $\Delta=3$} 的图的邻和可区别全可选性[J]. 数学进展, 2016, 45(3): 343-348.
Viewed
Full text

Abstract

Cited

Discussed