Date Available
4-28-2017
Year of Publication
2017
Degree Name
Doctor of Philosophy (PhD)
Document Type
Doctoral Dissertation
College
Arts and Sciences
Department/School/Program
Mathematics
First Advisor
Dr. Heide Gluesing-Luerssen
Abstract
Hamming-distance graphs arise naturally in the study of error-correcting codes and have been utilized by several authors to provide new proofs for (and in some cases improve) known bounds on the size of block codes. We study various standard graph properties of the Hamming-distance graphs with special emphasis placed on the chromatic number. A notion of robustness is defined for colorings of these graphs based on the tolerance of swapping colors along an edge without destroying the properness of the coloring, and a complete characterization of the maximally robust colorings is given for certain parameters. Additionally, explorations are made into subgraph structures whose identification may be useful in determining the chromatic number.
Digital Object Identifier (DOI)
https://doi.org/10.13023/ETD.2017.194
Recommended Citation
Harney, Isaiah H., "Colorings of Hamming-Distance Graphs" (2017). Theses and Dissertations--Mathematics. 49.
https://uknowledge.uky.edu/math_etds/49
