On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory

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.

Grantor dc:publisher

University of Tennessee at Chattanooga

Author dc:creator

• Plaisted, Daniel

Contributors dc:contributor

• Barioli, Francesco
• van der Merwe, Lucas; Nichols, Roger; Walters, Terry
• College of Arts and Sciences

• Graph theory
• Representations of graphs

Licence

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

Language dc:language

English, eng

Repository record dc:identifier

https://scholar.utc.edu/theses/611

OAI identifier oai:identifier

oai:scholar.utc.edu:theses-1773