Committee Chair

Barioli, Francesco

Committee Member

van der Merwe, Lucas; Nichols, Roger; Walters, Terry

Department

Dept. of Mathematics

College

College of Arts and Sciences

Publisher

University of Tennessee at Chattanooga

Place of Publication

Chattanooga (Tenn.)

Abstract

This thesis regards the minimum rank and minimum positive semidefinite rank of a simple graph. A graph parameter, called the minimum labeling degree (mld), is defined in terms of the concept of a vertex labeling of a graph, and its value is calculated for a few graph classes. It is proved here that there is a conception of mld that is independent of the notion of vertex labeling. Then, for a few other graph parameters β, including the zero-forcing number, a general inequality between mld and β is shown to hold. Further, it is demonstrated here that a certain upper bound for minimum rank in terms of minimum labeling degree holds for several classes of graphs for which minimum rank is known. Later, graphs whose complements both are K_{3,2}-free and have minimum labeling degree 2 are proved to have minimum positive semidefinite rank at most 4. Finally, two more labeling-independent conceptions of mld are given.

Acknowledgments

Thanks a lot to Dr. Barioli for the introduction to the problem and the minimum labeling degree parameter, and the good suggestions regarding the content of the document. Thanks also to Drs. Nichols, van der Merwe, and Walters for serving on the committee.

Degree

M. S.; A thesis submitted to the faculty of the University of Tennessee at Chattanooga in partial fulfillment of the requirements of the degree of Master of Science.

Date

8-2019

Subject

Graph theory; Representations of graphs

Keyword

Minimum rank; Vertex labeling; Delta conjecture; Treewidth; Orthogonal representation; Minimum degree

Document Type

Masters theses

DCMI Type

Text

Extent

ix, 58 leaves

Language

English

Rights

https://rightsstatements.org/page/InC/1.0/?language=en

License

http://creativecommons.org/licenses/by/4.0/

Download

Share

COinS