首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
  • 本地全文:下载
  • 作者:Jan Dreier ; Philipp Kuinke ; Peter Rossmanith
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:176
  • 页码:14:1-14:13
  • DOI:10.4230/LIPIcs.APPROX/RANDOM.2020.14
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Preferential attachment graphs are random graphs designed to mimic properties of real word networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We prove various structural asymptotic properties of this graph model. In particular, we show that the size of the largest r-shallow clique minor in Gⁿ_m is at most log(n)^{O(r²)}m^{O(r)}. Furthermore, there exists a one-subdivided clique of size log(n)^{1/4}. Therefore, preferential attachment graphs are asymptotically almost surely somewhere dense and algorithmic techniques developed for structurally sparse graph classes are not directly applicable. However, they are just barely somewhere dense. The removal of just slightly more than a polylogarithmic number of vertices asymptotically almost surely yields a graph with locally bounded treewidth.
  • 关键词:Random Graphs; Preferential Attachment; Sparsity; Somewhere Dense
国家哲学社会科学文献中心版权所有