scientific article; zbMATH DE number 1123788
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\).
- Characterisation of graphs with exclusive sum labelling
- The space complexity of sum labelling
- On the range of size of sum graphs \& integral sum graphs of a given order
- A sum labelling for the generalised friendship graph
- The sum number and the integral sum number of a generalization of the dancing version of the cocktail party graph
- On the mod sum number of \(H _{m,n }\)
- Minimal sum labeling of graphs
- The space complexity of sum labelling
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4379745)
