Digital Commons Network^™

Bipartite Density Of Generalized Petersen Graphs, Lisa Jordan Ewell

Electronic Theses and Dissertations

The bipartite density b(G) of a graph G with m edges is the maximum ratio [special characters omitted] where m0 is the number of edges in a bipartitesubgraph of G. In this study we determine the bipartite density of several classes of Generalized Petersen Graphs. These graphs are denoted by P(n, k), where n ≥ 3 and 1 ≤ k < n with n ≠ 2k. The Generalized Petersen Graph P(n, k) has vertices [special characters omitted] and edges [special characters omitted] where subscript addition is modulo n. We define subgraphs P'(n, k) of P( n, k) by deleting the edge vn –1v0 and the edges w iwi+k for n – k ≤ i ≤ n – 1. For P'(n, k) and many classes of P(n, k), we determine the exact number of edges which must be removed from P( n, k) to reduce it to a bipartite subgraph. In many classes of Generalized Petersen Graphs the exact bipartite density is derived. For example: b(P(n, k)) = 1 for n even, k odd; b(P(n, k)) = 1 – [special characters omitted] for n and k odd and n > k²; b(P( n, k)) is asymptotically 1 – [special characters omitted] for n odd, k even.