Electronic Theses and Dissertations

Date of Award


Document Type


Degree Name

M.S. in Mathematics



First Advisor

William Staton

Second Advisor

Micah B. Milinovich

Third Advisor

Talmadge James Reid

Relational Format



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.

Included in

Mathematics Commons



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.