Some News about the Independence Number of a Graph

For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G. Keywords: graph, independence. 1991 Mathematical Subject Classification: 05C35. 1 Introduction and Results Let G be a finite simple and undirected graph on V (G) = f1; 2; :::; ng with its edge set E(G). A subset I of V (G), such that the subgraph of G induced by I is edgeless, is called an independent set of G, and the maximum cardinality of an independent set of G is named the independence number ff(G) of G. N(i) and d i denote the set and the number of neighbours of i 2 V (G) in G, respectively, and let \Delta(G) = maxfd i j i 2 V (G)g and C n = f(x 1 ; x 2 ; :::; x n ) j 0 x i 1 ; i = 1; 2; :::; ng. For events A and B and for a random variable Z of an arbitrary random space, P (A) , P (AjB) and E(Z) denote the probability of A, the conditional probability of A giv..