The critical independence number and an independence decomposition

DOI10.1016/J.EJC.2010.10.004zbMATH Open1230.05226arXiv0912.2260OpenAlexW2067215932MaRDI QIDQ616388FDOQ616388

Authors: Sumit K. Garg 

Publication date: 7 January 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: An independent set $I_c$ is a extit{critical independent set} if $|I_c|-|N(I_c)|geq|J|-|N(J)|$, for any independent set $J$. The extit{critical independence number} of a graph is the cardinality of a maximum critical independent set. This number is a lower bound for the independence number and can be computed in polynomial-time. Any graph can be decomposed into two subgraphs where the independence number of one subgraph equals its critical independence number, where the critical independence number of the other subgraph is zero, and where the sum of the independence numbers of the subgraphs is the independence number of the graph. A proof of a conjecture of Graffiti.pc yields a new characterization of K"{o}nig-Egervary graphs: these are exactly the graphs whose independence and critical independence numbers are equal.

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

Recommendations

• A generalization of the independence number
• Bounds for the Independence Number of Critical Graphs
• scientific article; zbMATH DE number 866059
• On the independence number of random graphs
• Approximating the minimum maximal independence number
• Approximating the independence number via the \(\vartheta\)-function
• A note on critical independence reductions
• Independence number, connectivity and \((a,b,k)\)-critical graphs
• Independence number of hypergraphs under degree conditions
• Publication:4735212

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=K%EF%BF%BD%EF%BF%BDnig-Egerv%EF%BF%BD%EF%BF%BDry+graphs&go=Go K��nig-Egerv��ry graphs]

Mathematics Subject Classification ID

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?)
• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• A characterization of the graphs in which the transversal number equals the matching number
• Using critical sets to solve the maximum independent set problem
• On Finding Critical Independent and Vertex Sets
• A note on critical independence reductions

Cited In (22)

• A new eigenvalue bound for independent sets
• When is \(G^2\) a König-Egerváry graph?
• Two more characterizations of König-Egerváry graphs
• On an annihilation number conjecture
• On König-Egerváry collections of maximum critical independent sets
• Forbidden subgraphs and the König-Egerváry property
• On some conjectures concerning critical independent sets of a graph
• Graphs with equal independence and annihilation numbers
• Critical independent sets of König-Egerváry graphs
• Critical sets, crowns and local maximum independent sets
• Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited
• Critical and maximum independent sets of a graph
• Some more updates on an annihilation number conjecture: pros and cons
• Critical independent sets and König-Egerváry graphs
• On maximum matchings in König-Egerváry graphs
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• Monotonic properties of collections of maximum independent sets of a graph
• Title not available (Why is that?)
• New results relating independence and matchings
• Counterexamples to the characterisation of graphs with equal independence and annihilation number
• Regular graphs with equal matching number and independence number
• A characterization of König-Egerváry graphs using a common property of all maximum matchings

This page was built for publication: The critical independence number and an independence decomposition

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