Critical sets, crowns and local maximum independent sets

DOI10.1007/S10898-021-01094-ZMaRDI QIDQ2149605zbMATH OpenOpenAlexFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 29 June 2022

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.04587

zbMATH Keywords

matchingbipartite graphcritical setcrowngreedoidaugmentoidlocal maximum independent setKönig-Egerváry graph

Mathematics Subject Classification ID

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 $SsubseteqV(G)$ is independent (or stable) if no two vertices from $S$ are adjacent, and by $mathrmInd(G)$ we mean the set of all independent sets of $G$. A set $AinmathrmInd(G)$ is critical (and we write $AinCritIndep(G)$) if $leftvertAightvert-leftvertN(A)ightvert=maxleftvertIightvert-leftvertN(I)ightvert:IinmathrmInd(G)$, where $N(I)$ denotes the neighborhood of $I$. If $SinmathrmInd(G)$ and there is a matching from $N(S)$ into $S$, then $S$ is a crown, and we write $SinCrown(G)$. Let $Psi(G)$ be the family of all local maximum independent sets of graph $G$, i.e., $SinPsi(G)$ if $S$ is a maximum independent set in the subgraph induced by $ScupN(S)$. In this paper we show that $CritIndep(G)subseteqCrown(G)$ $subseteqPsi(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.

Recommendations

• Some characterizations of the natural exponential families in \(\mathbb{R}^2\) and related Laplace transforms
• Bivariate natural exponential families with linear diagonal variance functions
• Total positivity properties of the bivariate diagonal natural exponential families
• scientific article; zbMATH DE number 55912
• Sur une propriété des familles exponentielles naturelles de variance quadratique

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5037209 (Why is no real title available?)
• A characterization of the graphs in which the transversal number equals the matching number
• A combinatorial structure ensuring applicability of the dynamic programming method
• A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
• A new greedoid: The family of local maximum stable sets of a forest
• A note on critical independence reductions
• A parallel algorithm for computing the critical independence number and related sets
• An algorithmic characterization of antimatroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial properties of the family of maximum stable sets of a graph
• Correspondence between two antimatroid algorithmic characterizations
• Critical independent sets and König-Egerváry graphs
• Crown reductions for the minimum weighted vertex cover problem
• Crown structures for vertex cover kernelization
• Crowns in bipartite graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Greedoids
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Introduction to Greedoids
• Local maximum stable set greedoids stemming from very well-covered graphs
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• On Finding Critical Independent and Vertex Sets
• On maximum matchings in König-Egerváry graphs
• On the corona of two graphs
• Some covering concepts in graphs
• Some structural properties of very well-covered graphs
• The critical independence number and an independence decomposition
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• Uniquely restricted matchings
• Using critical sets to solve the maximum independent set problem
• Vertex packings: Structural properties and algorithms
• Very well covered graphs

Cited in

(5)

• The diagonal multivariate natural exponential families and their classification
• Bivariate natural exponential families with linear diagonal variance functions
• Critical relations of crowns in critical times of coronavirus depression
• Some more updates on an annihilation number conjecture: pros and cons
• Crowns in bipartite graphs

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)