Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids

Details Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids

2010-08-17

arxiv.org/abs/1008.2897v1

Computer Science

Discrete Mathematics

7 pages, 5 figures

Scientific paper

A \textit{maximum stable set} in a graph $G$ is a stable set of maximum cardinality. $S$ is a \textit{local maximum stable set} of $G$, and we write $S\in\Psi(G)$, if $S$ is a maximum stable set of the subgraph induced by $S\cup N(S)$, where $N(S)$ is the neighborhood of $S$. Nemhauser and Trotter Jr. (1975), proved that any $S\in\Psi(G)$ is a subset of a maximum stable set of $G$. In (Levit & Mandrescu, 2002) we have shown that the family $\Psi(T)$ of a forest $T$ forms a greedoid on its vertex set. The cases where $G$ is bipartite, triangle-free, well-covered, while $\Psi(G)$ is a greedoid, were analyzed in (Levit & Mandrescu, 2002),(Levit & Mandrescu, 2004),(Levit & Mandrescu, 2007), respectively. In this paper we demonstrate that if $G$ is a very well-covered graph of girth $\geq4$, then the family $\Psi(G)$ is a greedoid if and only if $G$ has a unique perfect matching.

Affiliated with

Also associated with

No associations

Rating

Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-397928