Fractional Independence Number

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

 alpha^*(G)=max_(w_i+w_j<=1 for e_(ij) in E; w_i in [0,1])sum_(v in V)w_i

where w_i=w(v_i) is the weight on the ith 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


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

Subject classifications