Generalized Rotation numbers

A rooted graph is a pair ( G,x ), where G is a simple undirected graph and x ∈ V ( G ). If G is rooted at x , its k th rotation number h k ( G,x ) is the minimum number of edges in a graph F of order | G | + k such that for every v ∈ V ( F ) we can find a copy of G in F with the root vertex x at v. When k = 0, this definition reduces to that of the rotation number h ( G,x ), which was introduced in [“On Rotation Numbers for Complete Bipartite Graphs,” University of Victoria, Department of Mathematics Report No. DM‐186‐IR (1979)] by E.J. Cockayne and P.J. Lorimer and subsequently calculated for complete multipartite graphs. In this paper, we estimate the k th rotation number for complete bipartite graphs G with root x in the larger vertex class, thereby generalizing results of B. Bollobás and E.J. Cockayne [“More Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory , Vol. 6 (1982), pp. 403–411], J. Haviland [“Cliques and Independent Sets,” Ph. D. thesis, University of Cambridge (1989)], and J. Haviland and A. Thomason [“Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory , Vol. 16 (1992), pp. 61–71]. © 1993 John Wiley & Sons, Inc.