| Digital Archive


Search the Digital Archive

Finding the Minimum Randic Index

Show full item record

Author: Kunkler, Sarah Joyce
Advisor: Kincaid, Rex K.
Committee Members: Lamar, M. Drew; Phillips, David; Lewis, Michael
Issued Date: 7/13/2012
Subjects: Randic Index
Graph Theory
URI: http://hdl.handle.net/10288/16708
Description: 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.
Degree: Bachelors of Science in Mathematics

Files in this item

Files Size Format View Description
thesis_main.pdf 1.233Mb PDF View/Open thesis

This item appears in the following Collection(s)

Show full item record

CC0 1.0 Universal Except where otherwise noted, this item's license is described as CC0 1.0 Universal