A note on Hamiltonicity of uniform random intersection graphs

被引:0
|
作者
Mindaugas Bloznelis
Irmantas Radavičius
机构
[1] Vilnius University,Faculty of Mathematics and Informatics
来源
Lithuanian Mathematical Journal | 2011年 / 51卷
关键词
random graph; random intersection graph; Hamilton cycle; clustering; 05C45; 05C80;
D O I
暂无
中图分类号
学科分类号
摘要
We consider a collection of n independent random subsets of [m] = {1, 2, . . . , m} that are uniformly distributed in the class of subsets of size d, and call any two subsets adjacent whenever they intersect. This adjacency relation defines a graph called the uniform random intersection graph and denoted by Gn,m,d. We fix d = 2, 3, . . . and study when, as n,m → ∞, the graph Gn,m,d contains a Hamilton cycle (the event denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ {G_{n,m,d}} \in \mathcal{H} $\end{document}). We show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = o(1) $\end{document} for d2nm−1− lnm − 2 ln lnm → −∞ and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = 1 - o(1) $\end{document} for 2nm−1− lnm − ln lnm → +∞.
引用
收藏
页码:155 / 161
页数:6
相关论文
共 50 条
  • [21] COLORING RANDOM INTERSECTION GRAPHS AND COMPLEX NETWORKS
    Behrisch, Michael
    Taraz, Anusch
    Ueckerdt, Michael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (01) : 288 - 299
  • [22] COMPONENT EVOLUTION IN GENERAL RANDOM INTERSECTION GRAPHS
    Bloznelis, Mindaugas
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (02) : 639 - 654
  • [23] The jamming constant of uniform random graphs
    Bermolen, Paola
    Jonckheere, Matthieu
    Moyal, Pascal
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2017, 127 (07) : 2138 - 2178
  • [24] Large random intersection graphs inside the critical window and triangle counts
    Wang, Minmin
    ELECTRONIC JOURNAL OF PROBABILITY, 2025, 30
  • [25] Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs
    Chen, Ailian
    Zhang, Liping
    FILOMAT, 2023, 37 (26) : 9039 - 9050
  • [26] A Note on the Conductance of the Binomial Random Intersection Graph
    Rybarczyk, Katarzyna
    Bloznelis, Mindaugas
    Jaworski, Jerzy
    ALGORITHMS AND MODELS FOR THE WEB GRAPH, WAW 2020, 2020, 12091 : 124 - 134
  • [27] A note on the width of sparse random graphs
    Do, Tuan Anh
    Erde, Joshua
    Kang, Mihyun
    JOURNAL OF GRAPH THEORY, 2024, 106 (02) : 273 - 295
  • [28] Hamiltonicity in Prime Sum Graphs
    Chen, Hong-Bin
    Fu, Hung-Lin
    Guo, Jun-Yi
    GRAPHS AND COMBINATORICS, 2021, 37 (01) : 209 - 219
  • [29] Hamiltonicity and colorings of arrangement graphs
    Felsner, S
    Hurtado, F
    Noy, M
    Streinu, I
    PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2000, : 155 - 164
  • [30] Hamiltonicity of complements of total graphs
    Ma, Guoyan
    Wu, Baoyindureng
    DISCRETE GEOMETRY, COMBINATORICS AND GRAPH THEORY, 2007, 4381 : 109 - +