Dissertation/Thesis Abstract

Spanning trees, toughness, and eigenvalues of regular graphs
by Wong, Wiseley, Ph.D., University of Delaware, 2013, 109; 3595000
Abstract (Summary)

Spectral graph theory is a branch of graph theory which finds relationships between structural properties of graphs and eigenvalues of matrices corresponding to graphs. In this thesis, I obtain sufficient eigenvalue conditions for the existence of edge-disjoint spanning trees in regular graphs, and I show this is best possible. The vertex toughness of a graph is defined as the minimum value of [special characters omitted], where S runs through all subsets of vertices that disconnect the graph, and c(G\S ) denotes the number of components after deleting S. I obtain sufficient eigenvalue conditions for a regular graph to have toughness at least 1, and I show this is best possible. Furthermore, I determine the toughness value for many families of graphs, and I classify the subsets S of each family for when this value is obtained.

Indexing (document details)
Advisor: Cioaba, Sebastian M.
Commitee: Cioaba, Sebastian, Coulter, Robert, Lazebnik, Felix, Shader, Bryan
School: University of Delaware
Department: Department of Mathematical Sciences
School Location: United States -- Delaware
Source: DAI-B 75/01(E), Dissertation Abstracts International
Subjects: Mathematics
Keywords: Eigenvalues, Graph theory, Graph toughness, Regular graphs, Spanning trees, Spectral graph theory
Publication Number: 3595000
ISBN: 978-1-303-39892-6
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy