Fractional Independence Number

The fractional independence number (Willis 2011), denoted (Shannon 1956, Acín et al. 2016) or (Willis 2011), also called the fractional packing number (Shannon 1956, Acín et al. 2016) or Rosenfeld number (Acín et al. 2016), is a graph parameter defined by relaxing the weight condition in the computation of the independence number from allowing only weights 0 and 1 to any real numbers in the interval .

In other words, the fractional independence number of a graph with vertex set and edge set

(1)

where is the weight on the th vertex. This is a linear program that can be solved efficiently. Furthermore, a maximum weighting can always be obtained using the weights (Nemhauser 1975, Willis 2011), meaning that the fractional independence number must be an integer or half-integer.

For a graph on nodes, the fractional independence number satisfies

			(2)
			(3)

where is the independence number (Willis 2011, p. 12).

Values for special classes of graphs include

			(4)
			(5)

where is a complete graph and is a wheel graph (Willis 2011, p. 12).