Daniel Thornton '10 Connectivity: Initial Data and Analysis

Steinhaus Graphs: Determining Connectedness
I propose an Honors Thesis in Computer Science, whose object is the attainment of the following numbers:

P(n, k) The number of Steinhaus graphs with n vertices, k of which are pendant vertices (having degree ρ = 1).

C(n, k ) The number of Steinhaus graphs with n vertices, which are k-connected but not
(k + 1)- connected (symbolically: for which κ(H) = k and κ(H) ≠ (k + 1)).

E(n, k) The number of Steinhaus graphs with n vertices, which are k-edge-connected but not
(k + 1)-edge-connected (symbolically: for which λ(H) = k and λ(H) ≠ (k + 1)).

P(n, k) has been examined by some graph theorists, but C(n, k) and E(n, k) have not yet been referenced in any graph theory journal literature. I plan to work with Josiah W. Davis, a Computer Science and Mathematics major. We will be advised by Dr. Simon Levy and Dr. Wayne Dymàček.

I plan to write in Java (JDK 1.6), and will develop most of the algorithms. Josiah, who in this project is pursuing an Honors Thesis in Mathematics, will implement algorithms to find P(n, k), while I will focus on C(n, k) and E(n, k). These will be brute-force attempts, whose results will be used by Josiah to attempt mathematical proof of the patterns underlying these numbers.

Faculty Advisors: Wayne Dymàček and Simon Levy