On optimum summable graphs (Q2508410)

For a graph \(G\) with \(\delta(G)>1\) and a positive integer \(k\), let \(G_k=G\cup\overline{K_k}\). The graph \(G_k\) is a sum graph if there exists an injective labeling \(L:V(G_k)\rightarrow N\) such that for any two distinct vertices \(u, v\), \(uv\in E(G_k)\) if and only if there exists \(w\in V(G_k)\) with \(L(w)=L(u)+L(v)\). The sum number \(\sigma(G)\) of a connected graph \(G\) is then defined as the smallest \(k\) for which \(G_k\) is a sum graph. A nontrivial connected graph \(G\) is called a \(k\)-optimum summable graph, where \(k\geq 1\), if \(\sigma(G)=\delta(G)=k\). In the present paper, it is shown that if \(G\) is a \(k\)-optimum summable graph of order \(n\), \(k\geq 3\), then \(n\geq 2k\) and the complete bipartite graph \(K_{n,n-k}\) is not a spanning subgraph of \(G\). There is also shown for some classes of graphs that they are \(k\)-optimum summable (1-optimum summable are certain tadpoles, and examples of 2-optimum and \(k\)-optimum, \(k\geq 3\), summable graphs are given too).