A graph is intrinsically knotted (IK) if for every embedding of the graph there exists a knotted cycle. Let G be a multipartite graph, and form the multipartite graph G by increasing the number of vertices in each of the parts except one and then deleting an edge. We show that if G is IK, then the resulting graph G is also IK. We use this idea to describe large families of IK multipartite graphs. In particular we use the fact that K5,5\2e is IK to show that a bipartite graph with 10 or more vertices (respectively 12 or more vertices) with exactly 5 (resp. 6) in one part and E(G) <= 4V(G)-17 (resp. E(G) <=5V(G)-27) is IK. Our method cant be improved since we also show that K5,5\3e is not IK in general.
Thomas Mattman, Department of Mathematics, California State University, ChicoTMattman@csuchico.edu
Collins, Chloe; Hake, Ryan; Petonic, Cara; and Sardagna, Laura
"Intrinsic Knotting of Partite Graphs,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 8
, Article 11.
Available at: http://scholar.rose-hulman.edu/rhumj/vol8/iss1/11