## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 23-29 |

Number of pages | 7 |

Journal | Graphs and Combinatorics |

Volume | 8 |

Issue number | 1 |

DOIs | |

State | Published - Mar 1992 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics