ISSN 1000-1239 CN 11-1777/TP

• 基础理论 •

### 随机图中k-独立集的相变性质

1. (贵州大学计算机科学与技术学院 贵阳 550025) (yjlu111@126.com)
• 出版日期: 2017-12-01
• 基金资助:
国家自然科学基金项目(61262006，61462001，61540050，61762019)；贵州省重大应用基础研究项目(JZ20142001)；贵州大学研究生创新基金项目(2016047)

### Phase Transition Properties of k-Independent Sets in Random Graphs

Lu Youjun, Xu Daoyun

1. (College of Computer Science and Technology, Guizhou University, Guiyang 550025)
• Online: 2017-12-01

Abstract: Phase transition property is one of the most important properties of the theory of Erds-Rényi random graphs. A subset of vertices is a k-independent set in a simple undirected graph G=(V,E) if the subset is an independent set containing k vertex. In order to understand the structural property of k-independent sets in Erds-Rényi random graphs, the phase transition properties of k-independent sets in Erds-Rényi random graphs are investigated in this paper. It is shown that the threshold probability is p\-c=1－n\+－2/k－1 for the existence of k-independent sets in random graph G(n,p) via the first moment method and the second moment method when 2≤k=ο(n). According to this fact that random graph G(n,p) is equivalent to random graph G(n,m) when m is close to pC\+2\-n, the threshold edge number is given by m\-c=［n(n－1)/2(1－n\+－2/k－1)］ for the existence of k-independent sets in random graph G(n,m). The simulation results show that the consistence between simulation and theoretical threshold value for the existence of k-independent sets in random graph G(n,p) and G(n,m) when 2≤k=ο(n), and the threshold value is related to the total number n of vertices and the number k of vertices of independent set. However, when k=ω(n), the theoretical threshold value is not consistent with the simulation threshold value for the existence of k-independent sets in random graph G(n,p) and G(n,m).