JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2019, Vol. 54 ›› Issue (4): 86-90.doi: 10.6040/j.issn.1671-9352.0.2017.652

Previous Articles     Next Articles

K4-factors in random graphs

ZHANG Wei-wei*, CAI Jian-sheng   

  1. School of Mathematics and Information Science, Weifang University, Weifang 261061, Shandong, China
  • Published:2019-04-08

PDF (PC)

472

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 K4. The minimal probability p=p(n) for which a random graph G(n,p)almost surely contains a K4-factor. For p=O(n-0.44), the random graph G(n,p)almost surely contains a K4-factor.

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

CLC Number: 

  • O157.5
[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.
[1] LIU Xin-sheng, WEI Zi-ying. An upper bound for the adjacent vertex-distinguishing star chromatic number of graphs [J]. J4, 2012, 47(2): 52-55.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LIU Fang-yuan, MENG Xian-jia, TANG Zhan-yong, FANG Ding-yi, GONG Xiao-qing. Android application protection based on smali code obfuscation[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(3): 44 -50 .
[2] LIAO Xiang-wen, ZHANG Ling-ying, WEI Jing-jing, GUI Lin, CHENG Xue-qi, CHEN Guo-long. User influence analysis of social media with temporal characteristics[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(3): 1 -12 .
[3] GU Shen-ming, LU Jin-lu, WU Wei-zhi, ZHUANG Yu-bin. Local optimal granularity selections in generalized multi-scale decision systems[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 1 -8 .
[4] ZHU Lin. Separated monic representations of quivers of type A4and RSS equivalences[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(2): 1 -8 .
[5] . Interval algorithm for mixed integer nonlinear two-level programming problems[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(2): 9 -17 .
[6] YAN Yan, HAO Xiao-hong. Differential privacy partitioning algorithm based on adaptive density grids[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 12 -22 .
[7] YE Xiao-ming, CHEN Xing-shu, YANG Li, WANG Wen-xian, ZHU Yi, SHAO Guo-lin, LIANG Gang. Anomaly detection model of host group based on graph-evolution events[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 1 -11 .
[8] Zhao-xia WU,Jia-qi WANG. Wireless single spectrum secure auction algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 51 -55 .
[9] WAN Peng-fei, GAO Xing-bao. Novel artificial bee colony algorithm based on objective space decomposition for solving multi-objective optimization problems[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 56 -66 .
[10] CAO Wei-dong, DAI Tao, YU Jin-biao, WANG Xiao-hong, SHI An-feng. Improvement on the solution of pressure equation based on alternating direction in chemical flooding model[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 88 -94 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd