Critical sets, crowns and local maximum independent sets

DOI10.1007/S10898-021-01094-ZzbMATH Open1504.05219arXiv2008.04587OpenAlexW3210797779MaRDI QIDQ2149605FDOQ2149605

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 29 June 2022

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

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.

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

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

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)

Cites Work

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

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)