Back to search

Virginia Commonwealth University

KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph

Abstract

dc:description.abstract

For 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 × 1

Rights

dc:rights
Statement dc:rights
  • © The Author

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Short, Taylor. KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph. Thesis thesis, https://doi.org/10.25772/0WGJ-TC54