Intrinsic Knotting of Partite Graphs
Chloe Collins, Ryan Hake, Cara Petonic, Laura Sardagna · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · 2007
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.