Bipartite Density of Generalized Petersen Graphs

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.

Name thesis:degree_name

M.S. in Mathematics

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2011

Author dc:creator

• Ewell, Lisa Jordan

Contributors dc:contributor

• William Staton
• Micah B. Milinovich
• Talmadge James Reid

• Bipartite Density
• Generalized Petersen Graphs
• Mathematics

Repository record dc:identifier

https://egrove.olemiss.edu/etd/1324

OAI identifier oai:identifier

oai:egrove.olemiss.edu:etd-2323