Graphs with equal independence and annihilation numbers
Given a graph \(G\) with degree sequence \((d_1, \dots, d_n)\), the annihilation number \(a(G)\) of \(G\) is the largest index \(a\) for which the sum \(\sum_{i=1}^a d_i\) is at most the number edges in \(G\). The annihilation number is a polynomial time computable upper bound on the independence number. In the paper under review, the authors give two characterizations of the graphs with equal independence numbers and annihilation numbers -- one in terms of the critical independence number and one in terms of König-Egerváry graphs, maximum independent sets, and maximum annihilation sets. Both characterizations imply that it can be determined in polymial time whether or not the independence number and annihilation number of a given graph are equal.
- On an annihilation number conjecture
- Some more updates on an annihilation number conjecture: pros and cons
- The critical independence number and an independence decomposition
- A characterization of König-Egerváry graphs using a common property of all maximum matchings
- Relating the annihilation number and the total domination number for some graphs
- Bounding the locating-total domination number of a tree in terms of its annihilation number
- Critical and maximum independent sets of a graph
- Relating the annihilation number and the 2-domination number of block graphs
- Regular graphs with equal matching number and independence number
- New results relating independence and matchings
- Some more updates on an annihilation number conjecture: pros and cons
- On the König deficiency of zero-reducible graphs
- On some conjectures concerning critical independent sets of a graph
- Largest domination number and smallest independence number of forests with given degree sequence
- scientific article; zbMATH DE number 3752895 (Why is no real title available?)
- Relating the annihilation number and the 2-domination number of a tree
- On the k-residue of disjoint unions of graphs with applications to k-independence
- A way to construct independence equivalent graphs
- On an annihilation number conjecture
- Inflated graphs with equal independence number and upper irredundance number
- Counterexamples to the characterisation of graphs with equal independence and annihilation number
- Efficiently recognizing graphs with equal independence and annihilation numbers
- On 1-König-Egerváry graphs
- Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited
This page was built for publication: Graphs with equal independence and annihilation numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640438)
