TOPICS
Search

Fractional Independence Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The fractional independence number alpha_f(G) is a graph parameter obtained by relaxing the weights in the computation of the independence number from 0 and 1 to real numbers in the interval [0,1] (Willis 2011).

For a graph G with vertex set V and edge set E, it is defined by

alpha_f(G)=max_(w_i+w_j<=1 for e_(ij) in E; w_i in [0,1])sum_(v_i in V)w_i,
(1)

where w_i=w(v_i) is the weight on the ith graph vertex. This can be computed using linear programming. A maximum weighting can always be obtained using the weights {0,1/2,1} (Nemhauser and Trotter 1975, Willis 2011), so the fractional independence number is an integer or half-integer.

For a graph on n vertices,

alpha_f(G)>=n/2
(2)
alpha_f(G)>=alpha(G),
(3)

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

Values for special classes of graphs include

alpha_f(K_n)=n/2
(4)
alpha_f(W_n)=n/2
(5)

for n>=2 and n>=4, respectively, where K_n is a complete graph and W_n is a wheel graph (Willis 2011, p. 12). The singleton graph K_1 has alpha_f(K_1)=1.

A related quantity, also called the fractional independence number in some sources, is the fractional packing number or Rosenfeld number alpha^*(G) (Shannon 1956, Acín et al. 2017). It imposes a constraint for every clique C, rather than only for every graph edge:

alpha^*(G)=max_(sum_(v_i in C)w_i<=1 for every clique C; w_i>=0)sum_(v_i in V)w_i.
(6)

The two quantities can differ: for the complete graph K_3, alpha_f(K_3)=3/2 while alpha^*(K_3)=1.

See also

Independence Number

Explore with Wolfram|Alpha

References

Acín, A.; Duan, R.; Roberson, D. E.; Sainz, A. B.; and Winter, A. "A New Property of the Lovász Number and Duality Relations between Graph Parameters." Disc. Appl. Math. 216, 489-501, 2017. https://doi.org/10.1016/j.dam.2016.04.028.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." Master's thesis. Richmond, VA: Virginia Commonwealth University, 2011. https://doi.org/10.25772/B95B-C733.

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