Critical sets, crowns and local maximum independent sets

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A set

S s u b s e t e q V (G)

is independent (or stable) if no two vertices from

S

are adjacent, and by

m a t h r m I n d (G)

we mean the set of all independent sets of

G

. A set

A i n m a t h r m I n d (G)

is critical (and we write

A i n C r i t I n d e p (G)

) if

l e f t v e r t A i g h t v e r t - l e f t v e r t N (A) i g h t v e r t = m a x l e f t v e r t I i g h t v e r t - l e f t v e r t N (I) i g h t v e r t : I i n m a t h r m I n d (G)

, where

N (I)

denotes the neighborhood of

I

. If

S i n m a t h r m I n d (G)

and there is a matching from

N (S)

into

S

, then

S

is a crown, and we write

S i n C r o w n (G)

. Let

P s i (G)

be the family of all local maximum independent sets of graph

G

, i.e.,

S i n P s i (G)

if

S

is a maximum independent set in the subgraph induced by

S c u p N (S)

. In this paper we show that

C r i t I n d e p (G) s u b s e t e q C r o w n (G)

s u b s e t e q P s i (G)

are true for every graph. In addition, we present some classes of graphs where these families coincide and form greedoids or even more general set systems that we call augmentoids.

Review text

Let \(G\) be a graph with vertex set \(V(G)\); denote the neighbors of \(U \subseteq V(G)\) by \(N(U)\). Three types of independent sets are studied. An independent set \(I\) is critical independent if \(|I|-|N(I)| \geq |J| - |N(J)|\) for any independent set \(J\); it is a crown if there exists a matching from \(N(I)\) to \(I\); and is local maximum independent if it is of maximum size in the subgraph induced by \(I \cup N(I)\). The authors study the interplay between these concepts and also König-Evergáry graphs. They show, in particular, that a critical independent set is a crown, which is in turn, local maximum independent. Generalizing a greedoid, they coin the useful concept of an augmentoid. An augmentoid consists of a non-empty family \(\mathcal F\) of subsets of a set \(E\) satisfying the following: for \(X,Y \in \mathcal F\), there exists \(A \subseteq X - Y\) and \(B \subseteq Y - X\) so that \(Y \cup A, X \cup B \in \mathcal F\) and \(|Y \cup A | = |X \cup B|\). Various examples of augmentoids are given, among them are the collection of crowns and of critical independent sets in the set \(V(G)\). Augmentoids enjoy the property that each of its elements can be enlarged to one which is maximal by inclusion. This concept is used to prove a number of new though not unexpected properties of the independent sets studied in the paper. Various relationships between these concepts and König-Evergáry graphs are exposed. The proofs are straightforward. The concept of an augmentoid appears primed for further study.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Critical sets, crowns and local maximum independent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149605)