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 条
  • [31] Threshold Functions in Random s-Intersection Graphs
    Zhao, Jun
    2015 53RD ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), 2015, : 1358 - 1365
  • [32] Hamiltonicity of complements of middle graphs
    An, Xinhui
    Wu, Baoyindureng
    DISCRETE MATHEMATICS, 2007, 307 (9-10) : 1178 - 1184
  • [33] Large independent sets in general random intersection graphs
    Nikoletseas, S.
    Raptopoulos, C.
    Spirakis, P.
    THEORETICAL COMPUTER SCIENCE, 2008, 406 (03) : 215 - 224
  • [34] DEGREE AND CLUSTERING COEFFICIENT IN SPARSE RANDOM INTERSECTION GRAPHS
    Bloznelis, Mindaugas
    ANNALS OF APPLIED PROBABILITY, 2013, 23 (03) : 1254 - 1289
  • [35] POISSON APPROXIMATION OF THE NUMBER OF CLIQUES IN RANDOM INTERSECTION GRAPHS
    Rybarczyk, Katarzyna
    Stark, Dudley
    JOURNAL OF APPLIED PROBABILITY, 2010, 47 (03) : 826 - 840
  • [36] Hamiltonicity in Prime Sum Graphs
    Hong-Bin Chen
    Hung-Lin Fu
    Jun-Yi Guo
    Graphs and Combinatorics, 2021, 37 : 209 - 219
  • [37] k-connectivity of uniform s-intersection graphs
    Bloznelis, Mindaugas
    Rybarczyk, Katarzyna
    DISCRETE MATHEMATICS, 2014, 333 : 94 - 100
  • [38] Hamiltonicity and colorings of arrangement graphs
    Felsner, Stefan
    Hurtado, Ferran
    Noy, Marc
    Streinu, Ileana
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (17) : 2470 - 2483
  • [39] Hamiltonicity of sparse pseudorandom graphs
    Ferber, Asaf
    Han, Jie
    Mao, Dingjia
    Vershynin, Roman
    COMBINATORICS PROBABILITY AND COMPUTING, 2025,
  • [40] Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity
    Qin, Yong
    Xiao, Wenjun
    Miklavic, Stefko
    DISCRETE MATHEMATICS, 2009, 309 (17) : 5426 - 5431