Intrinsic Knotting of Bipartite Graphs
Sophy F. Huck · California State University ScholarWorks (system-wide DSpace) · 2010
ABSTRACT INTRINSIC KNOTTING OF BIPARTITE GRAPHS by Sophy F. Huck Master of Science in Mathematics Education California State University, Chico Summer 2010 We further identify and categorize intrinsically knotted bipartite graphs. We are motivated by a conjecture that a bipartite graph is intrinsically knotted when the number of edges, E, is greater than or equal to four times the number of vertices, V , minus 17. Previous research by Collins et al. has shown that this is the best possible bound for bipartite graphs that have exactly five vertices in one part and at least five in the other. Our research verifies the conjecture for graphs that have exactly six vertices (respectively exactly seven) in one part and at least six (resp. exactly seven) in the other. We also provide similar bounds for all bipartite graphs.