Fractional Independence Number

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The fractional independence number (Willis 2011), denoted 👁 alpha^*
(Shannon 1956, Acín et al. 2016) or 👁 alpha_f
(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 👁 [0,1]
.

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

where 👁 w_i=w(v_i)
is the weight on the 👁 i
th vertex. This is a linear program that can be solved efficiently. Furthermore, a maximum weighting can always be obtained using the weights 👁 {0,1/2,1}
(Nemhauser 1975, Willis 2011), meaning that the fractional independence number must be an integer or half-integer.

For a graph on 👁 n
nodes, the fractional independence number satisfies

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

Values for special classes of graphs include

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

See also

Independence Number

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Fractional Independence Number

Cite this as:

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

Subject classifications