Electronic Theses and Dissertations

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.

Included in

Mathematics Commons

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.