Defense Date

2011

Document Type

Thesis

Degree Name

Master of Science

Department

Mathematical Sciences

First Advisor

Craig Larson

Abstract

For a graph $G$, let $\alpha (G)$ be the cardinality of a maximum independent set, let $\mu (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 $\alpha (G)$ is greater than the matching number $\mu (G)$, $\xi (G) \geq 1 + \alpha(G) - \mu (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 + \alpha (G[X]) - \mu (G[X])$. Furthermore $1 + \alpha (G[X]) - \mu (G[X]) \geq 1 + \alpha (G) - \mu (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.

Rights

© The Author

Is Part Of

VCU University Archives

Is Part Of

VCU Theses and Dissertations

Date of Submission

April 2011

Share

COinS