New Results on the Genus of Complete Graphs with Excised Edges and Parameterization of the Resulting Isomorphism Classes

Overview

Objectives/Goals This research project explores the effect on the genus of a complete graph Kv on v vertices when edges are removed and also explores how to classify the resulting graphs. The genus is an important characteristic of a graph, providing a single numerical measure of the complexity of the graph. Also of importance in graph theory is Kv, which is universal in the sense that all graphs are subgraphs of some Kv. Thus, understanding how the genus of Kv responds to the excision of edges is of major importance in graph theory. Methods/Materials Three major mathematical fields were used to study the genus of the graphs resulting from excising edges of Kv. Low dimensional topology was used to link the genus of a graph to surface theory, graph theory was used to establish bounds on the genus, and combinatorics were used to calculate the number of isomorphism classes of graphs obtained from Kv when edges are excised. Results Three major new results were established. The first considers how many edges can be removed from Kv without changing its genus. I was able to give a sharp answer to this problem by introducing a function F(v)= (v-2)(v-5)/2 mod 6. Then my first main result is that if F(v) or fewer edges are removed from Kv, then the genus of the resulting graph is the same as the genus of Kv. My second result is a general result, independent of the genus result, that parameterizes the isomorphism classes of graphs of the form Kv - h edges. This result states that these isomorphism classes are parameterized by the isomorphism classes of graphs with h edges, both connected and non-connected, and with no vertices of degree 0. My third result combines my first two results to parameterize the isomorphism classes of graphs of the form Kv - F(v) edges, which are then calculated. Thus this result explicitly classifies graphs derived from Kv by the removal of F(v) edges. By my first result, these graphs then have the same genus as Kv. Applications of these results to complex networks, such as social networks and the internet, are also given. Conclusions/Discussion This project gives new results in graph theory related to the stability of the genus of Kv with respect to the excision of edges. The parameterization of the isomorphism classes of the resulting graphs is calculated. These results can be extended in two directions, to other well-known classes of graphs and to the excision of edges that decrease the genus of Kv.

Competition history

• CSEF 2015 Mathematics & Software · Entry S1404

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2015 project