Electronic Theses and Dissertations

Date of Award

1-1-2011

Document Type

Dissertation

Degree Name

M.S. in Mathematics

Department

Mathematics

First Advisor

William Staton

Second Advisor

Micah B. Milinovich

Third Advisor

Talmage Reid

Relational Format

dissertation/thesis

Abstract

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

Share

COinS
 
 

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.