Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 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
    /   /   推荐

摘要 对于任意给定的正整数 $k$, 图 $G$ 的距离匹配数 $um_k(G)$ 是指任意两条边之间距离大于 $k$ 的最大边数的集合. 令 $G_{n,p}$ 为经典 Erd\H{o}s-Rènyi 随机图. Kang 和 Manggala 刻画得到了当 $k\geq 2$, 边概率为 $p=\frac{c}{n}$ 时稀疏 Erd\H{o}s-Rènyi 随机图距离匹配数 $um_k(G_{n,p})$ 的上界, 其中 $c$ 为足够大的常数. 本文第一次利用二阶矩方法获得当 $k\geq 2$ 时此类稀疏随机图距离匹配数的下界.
关键词 距离匹配数Erd\H{o}s-Rènyi随机图二阶矩方法    
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   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .