Generalized sum graphs

Harary [8] calls a finite, simple graph G a sum graph if one can assign to each v_i∈V(G) a label x_i so that {v_i, v_j}∈E(G) iff x_i+x_j=x_k for some k. We generalize this notion by replacing "x_i+x_j" with an arbitrary symmetric polynomial f(x_i, x_j). We show that for each f, not all graphs are "f-graphs". Furthermore, we prove that for every f and every graph G we can transform G into an f-graph via the addition of |E(G)| isolated vertices. This result is nearly best possible in the sense that for all f and for {Mathematical expression}, there is a graph G with n vertices and m edges which, even after the addition of m-O(n log n) isolated vetices, is not and f-graph.