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

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-397928

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.