Generalized sum graphs

Noga Alon, Edward R. Scheinerman

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

Harary [8] calls a finite, simple graph G a sum graph if one can assign to each vi∈V(G) a label xi so that {vi, vj}∈E(G) iff xi+xj=xk for some k. We generalize this notion by replacing "xi+xj" with an arbitrary symmetric polynomial f(xi, xj). 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 languageEnglish (US)
Pages (from-to)23-29
Number of pages7
JournalGraphs and Combinatorics
Volume8
Issue number1
DOIs
StatePublished - Mar 1 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Generalized sum graphs'. Together they form a unique fingerprint.

  • Cite this