Virginia Commonwealth University
AUTOMATED CONJECTURING ON THE INDEPENDENCE NUMBER AND MINIMUM DEGREE OF DIAMETER-2-CRITICAL GRAPHS
Abstract
dc:description.abstractA diameter-2-critical (D2C) graph is a graph with diameter two such that removing any edge increases the diameter or disconnects the graph. In this paper, we look at other lesser-studied properties of D2C graphs, focusing mainly on their independence number and minimum degree. We show that there exist D2C graphs with minimum degree strictly larger than their independence number, and that this gap can be arbitrarily large. We also exhibit D2C graphs with maximum number of common neighbors strictly greater than their independence number, and that this gap can be arbitrarily large. Furthermore, we exhibit a D2C graph whose number of distinct degrees in its degree sequence is strictly greater than its independence number. Additionally, we characterize D2C graphs with independence number 2 and show that all such graphs have independence number greater or equal to their minimum degree.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Mathematical Sciences
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Forkin, Joshua R.
- Contributors dc:contributor
-
- Craig Larson
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- © The Author
Identifiers
dc:identifier.*- Identifier
- https://scholarscompass.vcu.edu/etd/6994