The inducibility of blow-up graphs

被引：18
|
作者：
Hatami, Hamed [1 ]
Hirst, James [1 ]
Norine, Serguei [2 ]
机构：
[1] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada
[2] McGill Univ, Dept Math, Montreal, PQ H3A 2K6, Canada
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2014年 / 109卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Induced subgraphs; Inducibility; Blow-up; COMPLETE BIPARTITE GRAPHS; MAXIMAL NUMBER; SUBGRAPHS;
D O I：
10.1016/j.jctb.2014.06.005
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The blow-up of a graph is obtained by replacing every vertex with a finite collection of copies so that the copies of two vertices are adjacent if and only if the originals are. If every vertex is replaced with the same number of copies, then the resulting graph is called a balanced blow-up. We show that any graph which contains the maximum number of induced copies of a sufficiently large balanced blow-up of H is itself essentially a blow-up of H. This gives an asymptotic answer to a question in [2]. (C) 2014 Elsevier Inc. All rights reserved.
引用
收藏
页码：196 / 212
页数：17
相关论文
共 50 条
  • [31] BLOW-UP IN CITIES
    不详
    NEW REPUBLIC, 1967, 157 (6-7) : 5 - 7
  • [32] Blow-up Lemma
    János Komlós
    Gábor N. Sárközy
    Endre Szemerédi
    Combinatorica, 1997, 17 : 109 - 123
  • [33] Blow-up Lemma
    Komlos, J
    Sarkozy, GN
    Szemeredi, E
    COMBINATORICA, 1997, 17 (01) : 109 - 123
  • [34] Blow-Up: Photographs
    Marchi, V
    OEIL-MAGAZINE INTERNATIONAL D ART, 1999, (502): : 20 - 20
  • [35] BIPARTISAN BLOW-UP
    不详
    ECONOMIST, 1957, 185 (10): : 864 - 864
  • [36] IMPLEMENTS OF GRAPH BLOW-UP IN CO-MAXIMAL IDEAL GRAPHS
    Ye, Meng
    Wu, Tongsuo
    Liu, Qiong
    Yu, Houyi
    COMMUNICATIONS IN ALGEBRA, 2014, 42 (06) : 2476 - 2483
  • [37] Blow-up phenomenon to the semilinear heat equation for unbounded Laplacians on graphs
    Lin, Yong
    Liu, Shuang
    Wu, Yiting
    REVISTA MATEMATICA COMPLUTENSE, 2025, 38 (01): : 281 - 294
  • [38] Blow-up conditions for a semilinear parabolic system on locally finite graphs
    Yiting Wu
    Acta Mathematica Scientia, 2024, 44 : 609 - 631
  • [39] BLOW-UP CONDITIONS FOR A SEMILINEAR PARABOLIC SYSTEM ON LOCALLY FINITE GRAPHS
    吴艺婷
    Acta Mathematica Scientia, 2024, 44 (02) : 609 - 631
  • [40] Blow-up of solutions for nonlinear wave equations on locally finite graphs
    Hong, Desheng
    AIMS MATHEMATICS, 2023, 8 (08): : 18163 - 18173
12345