Premium
The inducibility of complete bipartite graphs
Author(s) -
Brown Jason I.,
Sidorenko Alexander
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180610
Subject(s) - combinatorics , mathematics , multipartite , bipartite graph , complete bipartite graph , discrete mathematics , pancyclic graph , graph , cograph , 1 planar graph , chordal graph , physics , quantum mechanics , quantum entanglement , quantum
For any s ≥ 1 and t ≥ ( S 2 ), we prove that among all graphs with n vertices the graph that contains the maximal number of induced copies of K t , t + s for any fixed s ≥ 1 and t ≥ ( s 2 ) is K ( n /2)+α( n /2)‐α for some function α = o ( n ). We show that this is not valid for t < ( s 2 ). Analogous results for complete multipartite graphs are also obtained.