No label defined (Q4379745)

A graph is called a sum graph if there exists a labelling of its vertices by distinct positive integers such that the vertices labeled \(u\) and \(v\) are adjacent iff there exists a vertex labeled \(u+v\). It is easily seen that any graph can be transformed into a sum graph by adding to it a finite number of isolated vertices. A minimum number of such vertices is called the sum number of the graph \(G\) and denoted by \(\sigma(G)\). It is known that there exist graphs with \(\sigma(G)=\Theta(| V| ^2)\). However, no constructions of such graphs are presently known. Attempts to construct such graphs lead to the consideration of dense graphs. The authors conjecture that the complete multipartite graphs \(H_{m,n}\) with \(n\) independent sets consisting of \(m\) vertices each have large sum numbers. They show \(\sigma(H_{m,n})\in \Omega(mn)\) and \(\sigma(H_{m,n})\in O(mn^2)\). For \(m=2\) they present optimal numberings and prove that \(\sigma(H_{2,n})=4n-5\).