The Critical Independence Number and an Independence Decomposition

Details The Critical Independence Number and an Independence Decomposition The Critical Independence Number and an Independence Decomposition

2009-12-11

arxiv.org/abs/0912.2260v1

Mathematics

Combinatorics

10 pages, 4 figures

Scientific paper

An independent set $I_c$ is a \textit{critical independent set} if $|I_c| - |N(I_c)| \geq |J| - |N(J)|$, for any independent set $J$. The \textit{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.

Affiliated with

Also associated with

No associations

Rating

The Critical Independence Number and an Independence Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Critical Independence Number and an Independence Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Critical Independence Number and an Independence Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-468543