Dissertation/Thesis Abstract

On alpha-critical graphs and their construction
by Small, Benjamin Luke, Ph.D., Washington State University, 2015, 34; 3717480
Abstract (Summary)

A graph G is α-critical (or removal-critical) if α(G–e) = α(G)+1 for all edges ∈ 2 E(G), where α( G) is the vertex independence number of G. Similarly, a graph G is contraction-critical if α(G\e ) = α(G) – 1 for all edges e ∈ (G). This document discusses certain properties of removal-critical and contractioncritical graphs, and the enumeration of such graphs (up to 13 vertices and 17 vertices, respectively). It also discusses methods of constructing removal-critical graphs from smaller removal-critical graphs, including vertex duplication, splicing, buckling, and 1-joining. Finally, it discusses the number of removal-critical graphs that can or cannot be produced using these constructions.

Indexing (document details)
Advisor: Hudelson, Matthew
Commitee: McDonald, Judith J., Tsatsomeros, Michael
School: Washington State University
Department: Mathematics
School Location: United States -- Washington
Source: DAI-B 76/11(E), Dissertation Abstracts International
Subjects: Mathematics
Keywords: Alpha critical graphs, Removal-critical graphs
Publication Number: 3717480
ISBN: 978-1-321-96968-9
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy