On integral sum graphs (Q5906406)
From MaRDI portal
scientific article; zbMATH DE number 1321854
Language | Label | Description | Also known as |
---|---|---|---|
English | On integral sum graphs |
scientific article; zbMATH DE number 1321854 |
Statements
On integral sum graphs (English)
0 references
18 January 2000
0 references
For a finite subset \(S\) of \(\mathbb{N}^{*}\) the sum graph \(G(S)\) is the graph \((S,E)\) with \(uv\in E\) iff \(u+v\in S\). The sum number \(\sigma(G)\) of a graph \(G\) is the smallest nonnegative integer \(s\) such that \(G\cup sK_1\) is a sum graph. Similarly integral sum graphs with \(S\subset\mathbb{Z}\) instead of \(\mathbb{N}^{*}\), and the integral sum number \(\zeta(G)\) of a graph \(G\) are defined. Obviously, \(\zeta(G)\leq\sigma(G)\). The authors prove a conjecture of Harary that \(\zeta(G)=\sigma(G)\) for all complete graphs \(K_n\) with \(n\geq 4\). Another result disproves the conjecture that \(\zeta(G)=0\) implies \(G\) is a caterpillar, as it is shown that \(\zeta(G)=0\) for any quasistar of degree 3.
0 references
sum graph
0 references
integral sum number
0 references
tree
0 references
complete graph
0 references
caterpillar
0 references