Premium
Generalized Rotation numbers
Author(s) -
Chapman Robin J.,
Haviland Julie
Publication year - 1993
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.3190170304
Subject(s) - combinatorics , mathematics , bipartite graph , vertex (graph theory) , multipartite , complete bipartite graph , discrete mathematics , crossing number (knot theory) , graph , physics , intersection (aeronautics) , quantum mechanics , quantum entanglement , engineering , quantum , aerospace engineering
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.