TOPICS

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).

Independence NUmber

Explore with Wolfram|Alpha

More things to try:

References

Acín, A.; Duan, R.; Roberson, D. E.; Belén Sainz, A.; and Winter, A. "a New Property of the Lovász Number and Duality Relations Between Graph Parameters." 5 Feb 2016. https://arxiv.org/abs/1505.01265.Nemhauser, G. L. and Trotter, L. E. Jr. "Vertex Packings: Structural Properties and Algorithms." Math. Programming 8, 232-248, 1975.Shannon, C. E. "The Zero-Error Capacity of a Noisy Channel." IRE Trans. Inform. Th. 2, 8-19, 1956.Willis, W. "Bounds for the Independence Number of a Graph." Masters thesis. Richmond, VA: Virginia Commonwealth University, 2011.

Cite this as:

Weisstein, Eric W. "Fractional Independence Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FractionalIndependenceNumber.html