Search
next up previous
Next: David Fisher - The Up: Extremal Combinatorics / Combinatoire Previous: Aart Blokhuis, Ralph Faudree,

Jason Brown - The inducibility of complete bipartite graphs



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.