Date of Award
1-1-2013
Document Type
Dissertation
Degree Name
Ph.D. in Mathematics
Department
Mathematics
First Advisor
William Staton
Second Advisor
Talmadge James Reid
Third Advisor
Dawn Wilkins
Relational Format
dissertation/thesis
Abstract
A graph is called well-covered if all of its maximal independent sets have the same cardinality. We give a characterization of well-covered k-trees. A graph is said to be uniquely χ-colorable if, modulo permutations of colors, it has exactly one proper χ-coloring. The k-trees with at least k+1 vertices are minimal uniquely (k +1)-colorable, i.e., they have the minimal number of edges necessary for uniquely (k+1)-colorable graphs. We introduce the k-frames, a new class of minimal uniquely (k+1)-colorable graphs that generalizes the k-trees.
The covering range of a graph is the difference between the cardinality of a largest maximal independent set of a graph and the cardinality of a smallest maximal independent set of the graph. We give the covering range for some cubic graphs and a class of k-regular graphs.
Recommended Citation
Payne, Wanda Renea, "Well-covered Graphs, Unique Colorability, and Covering Range" (2013). Electronic Theses and Dissertations. 1439.
https://egrove.olemiss.edu/etd/1439