#### 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