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.
| Identifer | oai:union.ndltd.org:uky.edu/oai:uknowledge.uky.edu:math_etds-1048 |
| Date | 01 January 2017 |
| Creators | Harney, Isaiah H. |
| Publisher | UKnowledge |
| Source Sets | University of Kentucky |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations--Mathematics |
Page generated in 0.014 seconds