随机图中的K4-因子

doi:10.6040/j.issn.1671-9352.0.2017.652

《山东大学学报(理学版)》 ›› 2019, Vol. 54 ›› Issue (4): 86-90.doi: 10.6040/j.issn.1671-9352.0.2017.652

随机图中的K₄-因子

张伟伟^*,蔡建生

潍坊学院数学与信息科学学院, 山东潍坊 261061

发布日期:2019-04-08
作者简介:张伟伟(1986— ),女,博士研究生,讲师,研究方向为图论. E-mail:zhangww8@163.com通信作者*
基金资助:
国家自然科学基金资助项目(11571258,31601079)

K₄-factors in random graphs

ZHANG Wei-wei^*, CAI Jian-sheng

School of Mathematics and Information Science, Weifang University, Weifang 261061, Shandong, China

Published:2019-04-08

摘要/Abstract

摘要： 设图G具有n个顶点, 图的K₄-因子是由n/4个顶点互不相交的K₄构成的图G的子图(其中 4 整除 n)。我们试图寻找尽可能小的概率使得随机图G几乎必然包含K₄-因子。应用概率方法,给出当概率p=O(n^-0.44)时, 随机图G(n,p)几乎必然包含K₄-因子。

关键词: 随机图, K₄-因子, 概率方法, Janson不等式

Abstract: For a graph G with n vertices, where 4 divides n, a K4-factor is a subgraph of G, consisting of(n)/4 vertex disjoint K₄. The minimal probability p=p(n) for which a random graph G(n,p)almost surely contains a K₄-factor. For p=O(n^-0.44), the random graph G(n,p)almost surely contains a K4-factor.

Key words: random graphs, K₄-factors, probabilistic method, Janson inequality

中图分类号:

O157.5

张伟伟,蔡建生. 随机图中的K₄-因子[J]. 《山东大学学报(理学版)》, 2019, 54(4): 86-90.

ZHANG Wei-wei, CAI Jian-sheng. K₄-factors in random graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(4): 86-90.

参考文献

[1] ERDOS P, RENYI A. On the existence of a factor of degree one in a connected random graph[J]. Acta Math Acad Sci. Hungar. 1996, 17: 359-368.
[2] KRIVELEVICH M. Triangle factors in random graphs[J]. Combinatorics, Probability and Computing, 1997, 6:337-347.
[3] AION N, YUSTER R. Threshold functions for H-factors[J]. Combinatorics, Probability and Computing, 1993, 2:137-144.
[4] RUCINSKI A. Matching and covering the vertices of a random graph by copies of a given graph[J]. Discrete Math, 1992, 106:185-197.
[5] AION N, SPENCER J H. The probabilistic method[M]. New York: Wiley, 1992: 303-335.
[6] JANSON S, LUCZAK T, RUCINSKI A. An exponential bound for the probability of nonexistence of a specified subgraph in a random graph[J]. Random Graphs, 1990, 87:73-87.
[7] 蔡建生, 闫桂英. 随机图中[k, k+1] -因子的存在性[J]. 应用数学学报, 2017, 40(1):144-148. CAI Jiansheng, YAN Guiying. On the existence of[k, k+1] -factors in random graphs[J]. Acta Mathematicae Applicatae Sinica, 2017, 40(1):144-148.
[8] CAI J S, WANG X Y, YAN G Y. A note on the existence of fractional f-factors in random graphs[J]. Acta Mathematicae Applicatae Sinica, English Series, 2014, 30(3):677-680.
[9] YAN Y Z, WANG H X, WANG J, et al. H(n)-factors in random graphs[J]. Statistics & Probability Letters, 2008, 78(11):1255-1258.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

本文评价

推荐阅读 10

[1]	刘方圆,孟宪佳,汤战勇,房鼎益,龚晓庆. 基于smali代码混淆的Android应用保护方法Symbol`@@[J]. 山东大学学报（理学版）, 2017, 52(3): 44 -50 .
[2]	廖祥文,张凌鹰,魏晶晶,桂林,程学旗,陈国龙. 融合时间特征的社交媒介用户影响力分析[J]. 山东大学学报（理学版）, 2018, 53(3): 1 -12 .
[3]	顾沈明,陆瑾璐,吴伟志,庄宇斌. 广义多尺度决策系统的局部最优粒度选择[J]. 山东大学学报（理学版）, 2018, 53(8): 1 -8 .
[4]	朱林. A₄型箭图的可分单态射表示和RSS等价[J]. 山东大学学报（理学版）, 2018, 53(2): 1 -8 .
[5]	刘园园,曹德欣,秦军. 非线性二层混合整数规划问题的区间算法[J]. 山东大学学报（理学版）, 2018, 53(2): 9 -17 .
[6]	晏燕,郝晓弘. 差分隐私密度自适应网格划分发布方法[J]. 山东大学学报（理学版）, 2018, 53(9): 12 -22 .
[7]	叶晓鸣,陈兴蜀,杨力,王文贤,朱毅,邵国林,梁刚. 基于图演化事件的主机群异常检测模型[J]. 山东大学学报（理学版）, 2018, 53(9): 1 -11 .
[8]	巫朝霞,王佳琪. 一种无线单频谱安全拍卖算法[J]. 《山东大学学报(理学版)》, 2018, 53(11): 51 -55 .
[9]	万鹏飞,高兴宝. 一种解多目标优化问题的基于分解的人工蜂群算法[J]. 山东大学学报 (理学版), 2018, 53(11): 56 -66 .
[10]	曹伟东,戴涛,于金彪,王晓宏,施安峰. 化学驱模型中压力方程的交替方向解法改进[J]. 山东大学学报（理学版）, 2018, 53(10): 88 -94 .

随机图中的K₄-因子

K₄-factors in random graphs

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 10

[1]	刘信生,魏自盈. 图的邻点可区别星边色数的一个上界[J]. J4, 2012, 47(2): 52-55.
[2]	刘信生朱志强. 图的点可区别IE-全色数的一个上界[J]. J4, 2009, 44(10): 14-16.