Date Thesis Awarded

7-2012

Document Type

Honors Thesis

Degree Name

Bachelors of Science (BS)

Department

Mathematics

Advisor

Rex K. Kincaid

Committee Member

M. Drew Lamar

Committee Member

David Phillips

Committee Member

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.

Share

COinS