Computer Science – Discrete Mathematics
Scientific paper
2010-08-17
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.
Levit Vadim E.
Mandrescu Eugen
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-397928