Nonvertex-Balanced Factors in Random Graphs

被引：8
|
作者：
Gerke, Stefanie [1 ]
McDowell, Andrew [1 ]
机构：
[1] Univ London, Royal Holloway Coll, Dept Math, Egham TW20 0EX, Surrey, England
来源：
JOURNAL OF GRAPH THEORY | 2015年 / 78卷 / 04期
关键词：
random graphs; factors; digraphs;
D O I：
10.1002/jgt.21805
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1-28.) regarding threshold functions for the existence of an H-factor in a random graph G(n,p). We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1-28) generalizes to multigraphs, digraphs, and a multipartite model.
引用
收藏
页码：269 / 286
页数：18
相关论文
共 50 条
  • [1] STRONGLY BALANCED GRAPHS AND RANDOM GRAPHS
    RUCINSKI, A
    VINCE, A
    JOURNAL OF GRAPH THEORY, 1986, 10 (02) : 251 - 264
  • [2] On balanced coloring games in random graphs
    Gugelmann, Luca
    Spoehel, Reto
    EUROPEAN JOURNAL OF COMBINATORICS, 2014, 35 : 297 - 312
  • [3] Balanced Allocation on Graphs: A Random Walk Approach
    Pourmiri, Ali
    COMPUTING AND COMBINATORICS, COCOON 2016, 2016, 9797 : 330 - 341
  • [4] Balanced cut approximation in random geometric graphs
    Diaz, Josep
    Grandoni, Fabrizio
    Spaccamela, Alberto Marchetti
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2006, 4288 : 527 - +
  • [5] Balanced cut approximation in random geometric graphs
    Diaz, Josep
    Grandoni, Fabrizio
    Spaccamela, Alberto Marchetti
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (27-29) : 2725 - 2731
  • [6] Balanced online Ramsey games in random graphs
    Prakash, Anupam
    Spoehel, Reto
    Thomas, Henning
    ELECTRONIC JOURNAL OF COMBINATORICS, 2009, 16 (01):
  • [7] Balanced allocation on graphs: A random walk approach
    Pourmiri, Ali
    RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (04) : 980 - 1009
  • [8] Factors in random graphs
    Johansson, Anders
    Kahn, Jeff
    Vu, Van
    RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (01) : 1 - 28
  • [9] ON FACTORS IN RANDOM GRAPHS
    SHAMIR, E
    UPFAL, E
    ISRAEL JOURNAL OF MATHEMATICS, 1981, 39 (04) : 296 - 302
  • [10] Balanced Allocation on Graphs with Random Walk Based Sampling
    Tang, Dengwang
    Subramanian, Vijay G.
    2018 56TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), 2018, : 765 - 766
12345