Date Thesis Awarded

7-2012

Access Type

Honors Thesis -- Access Restricted On-Campus Only

Degree Name

Bachelors of Science (BS)

Department

Mathematics

Advisor

Rex K. Kincaid

Committee Members

M. Drew Lamar

David Phillips

Michael Lewis

Abstract

We show that finding a graph realization with the minimum Randic index for a given degree sequence is solvable in polynomial time. This is shown by reducing the problem to the minimum weight perfect b-matching problem. Using the b-matching problem, we find the realization with the minimum Randic index, but this graph is not guaranteed to be connected. In this case, we have developed a heuristic to connect the graph using two-switches, which preserves the degree sequence. From our experiments, the Randic index of the realization after our heuristic has a much lower percent difference from the minimum Randic index than that between the original and the minimum Randic index.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Public Domain Dedication 1.0 License.

Comments

Thesis is part of Honors ETD pilot project, 2008-2013. Migrated from Dspace in 2016.

Download

Share Feedback

On-Campus Access Only

Share

COinS