I've tried the following LP relaxation of maximum independent set$$\max \sum_i x_i$$$$\text{s.t.}\  x_i+x_j\le 1\  \forall (i,j)\in E$$$$x_i\ge 0$$I get $1/2$ for every variable for every cubic non-bipartite graph I tried.Is true for all connected cubic non-bipartite graphs?Is there LP relaxation which works better for such graphs?Update 03/05:Here's the result of clique-based LP relaxation suggested by Nathanhttp://yaroslavvb.com/blog/blog-lp/clique-lp.pngI've summarized experiments here  Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.
LP relaxation of independent set
graph theory;co.combinatorics;linear programming
Non-bipartite connected cubic graphs have the unique optimal solution $x_i = 1/2$; in a bipartite cubic graph you have an integral optimal solution.Proof: In a cubic graph, if you sum over all $3n/2$ constraints $x_i + x_j \le 1$, you have $\sum_i 3 x_i \le 3n/2$, and hence the optimum is at most $n/2$.The solution $x_i = 1/2$ for all $i$ is trivially feasible, and hence also optimal.In a bipartite cubic graph, each part has half of the nodes, and the solution $x_i = 1$ in one part is hence also optimal.Any optimal solution must be tight, that is, we must have $\sum_i 3 x_i = 3n/2$ and hence $x_i + x_j = 1$ for each edge $\{i,j\}$. Thus if you have an odd cycle, you must choose $x_i = 1/2$ for each node in the cycle. And then if the graph is connected, this choice gets propagated everywhere.