A family of sparse graphs of large sum number (Q1894767)

Given an (undirected) graph \(G= (V, E)\), and an integer \(r\geq 0\), \(G_r= (V_r, E)\) is obtained by adding \(r\) isolated vertices to \(G\). \(G_r\) is said to be a sum graph, if one can label the vertices \(v\in V_r\) with distinct positive integers \(L(v)\), such that for every pair of distinct vertices \(v,w\in V_r\), \((v,w)\in E\), if and only if there exists a vertex \(x\in V_r\) with \(L(x)= L(v)+ L(w)\). The sum number of a graph \(G\) is the smallest \(r\), such that \(G_r\) is a sum graph. In this paper, the authors consider the sum number of wheel graphs: graphs obtained by taking a circuit, and adding one vertex adjacent to each vertex in the circuit. They show, that for sufficiently large \(n\), a wheel with \(n+1\) vertices has sum number \(n/2+3\), if \(n\) is even, and sum number between \(n\) and \(n+2\), if \(n\) is odd. This is the first example of a class for which it is known that the sum number is proportional to the size of the graphs.