Dissertation
On alpha-critical graphs and their construction
Doctor of Philosophy (PhD), Washington State University
01/2015
Handle:
https://hdl.handle.net/2376/111310
Abstract
A graph $G$ is $\\\\alpha$-critical (or removal-critical) if $\\\\alpha(G-e)=\\\\alpha(G)+1$ for all edges $e\\\\in E(G)$, where $\\\\alpha(G)$ is the vertex independence number of $G$. Similarly, a graph $G$ is contraction-critical if $\\\\alpha(G\\\\setminus e)=\\\\alpha(G)-1$ for all edges $e\\\\in E(G)$. This document discusses certain properties of removal-critical and contraction-critical graphs, and the enumeration of such graphs (up to 13 vertices and 16 vertices, respectively). It also discusses methods of constructing removal-critical graphs from smaller removal-critical graphs: `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.
Metrics
15 File views/ downloads
25 Record Views
Details
- Title
- On alpha-critical graphs and their construction
- Creators
- Benjamin Small
- Contributors
- Matthew Hudelson (Advisor)Judith J McDonald (Committee Member)Michael Tsatsomeros (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Mathematics and Statistics, Department of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Number of pages
- 34
- Identifiers
- 99900581529101842
- Language
- English
- Resource Type
- Dissertation