Next: David Fisher - The Up: Extremal Combinatorics / Combinatoire Previous: Aart Blokhuis, Ralph Faudree,
|JASON BROWN, Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia B3H 3J5, Canada|
|The inducibility of complete bipartite graphs|
Given a fixed graph G, it is a natural extremal problem to ask: among all graphs of order n, which have the maximum number of induced subgraphs isomorphic to G? Furthermore, what is this maximum number? How can it be estimated? We examine here these problems for complete bipartite graphs. Surprisingly, the extremal graphs are not always complete bipartite graphs with equal (or nearly equal) parts. Some extensions to the multipartite case will also be noted.