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 条
12345