Virginia Commonwealth University
KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph
Abstract
dc:description.abstractFor a graph $G$, let α (G) be the cardinality of a maximum independent set, let μ (G) be the cardinality of a maximum matching and let $\xi (G)$ be the number of vertices belonging to all maximum independent sets. Boros, Golumbic and Levit showed that in connected graphs where the independence number α (G) is greater than the matching number μ (G), \xi (G) \geq 1 + α(G) - μ (G). For any graph $G$, we will show there is a distinguished induced subgraph $G[X]$ such that, under weaker assumptions, \xi (G) \geq 1 + α (G[X]) - μ (G[X]). Furthermore 1 + α (G[X]) - μ (G[X]) \geq 1 + α (G) - μ (G) and the difference between these bounds can be arbitrarily large. Lastly some results toward a characterization of graphs with equal independence and matching numbers is given.
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
-
- Short, Taylor
- 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/2353