文章基本信息

标题：Thresholds in Random Motif Graphs
本地全文：下载
作者：Michael Anastos ; Peleg Michaeli ; Samantha Petti 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-19
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.66
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We introduce a natural generalization of the Erdös-Rényi random graph model in which random instances of a fixed motif are added independently. The binomial random motif graph G(H,n,p) is the random (multi)graph obtained by adding an instance of a fixed graph H on each of the copies of H in the complete graph on n vertices, independently with probability p. We establish that every monotone property has a threshold in this model, and determine the thresholds for connectivity, Hamiltonicity, the existence of a perfect matching, and subgraph appearance. Moreover, in the first three cases we give the analogous hitting time results; with high probability, the first graph in the random motif graph process that has minimum degree one (or two) is connected and contains a perfect matching (or Hamiltonian respectively).
关键词：Random graph; Connectivity; Hamiltonicty; Small subgraphs