The spum and sum-diameter of graphs: labelings of sum graphs (Q2113361)

A graph labeling is an assignment of integers to the vertices or edges, or both, subject to certain conditions. Graph labelings were first introduced in the mid-1960s. \textit{F. Harary} [Congr. Numerantium 72, 101--108 (1990; Zbl 0691.05038)] defined a sum graph to be a graph whose vertices can be labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label in the graph. Not every graph is a sum graph: the vertex with the highest label must be isolated, so any graph without isolated vertices cannot be a sum graph. However, if one adds enough isolated vertices to a graph it will become possible to represent it as a sum graph, and Harary analyzed the minimum number of isolated vertices one must add to an (unlabeled) graph so that it can be represented as a sum graph, which he called the sum number \(\sigma(G)\). The sum number of various special families of graphs have been identified, notably including complete graphs \(K_n\), cycles \(C_n\), and trees. \textit{J. A. Gallian} [Electron. J. Comb. DS06, Research paper DS6, 43 p. (1998; Zbl 0953.05067)] brought out a survey on graph labeling. His survey contains a comprehensive list of known results on the sum number. \textit{F. Harary} [Discrete Math. 124, No. 1--3, 99--105 (1994; Zbl 0797.05069)] extended his notion of a sum graph to allow distinct integer labels, rather than simply positive integers; the corresponding graph is called an integral sum graph, and the corresponding integral sum number is denoted \(\varsigma (G)\). In the year 1990, \textit{J. Goodell} et al. [``Sum graphs'' (unpublished)] introduced the notion of spum. It is the minimum possible difference between the maximum and the minimum labels for a labeling of the sum graph obtained by adding \(\sigma(G)\) isolated vertices to \(G\). Recently \textit{S. Singla} et al. [Discrete Math. 344, No. 5, Article ID 112311, 13 p. (2021; Zbl 1460.05166)] calculated \(spum(K_n) = 4n -6 \) for \(n \geq 2\), as well as the spum for other families of graphs, such as \(K_{1,n}\) and \(K_{(n,n)}\), and bounding the spum of paths \(P_n\) and cycles \(C_n\). They also introduced the natural integral variant of spum, where integral spum concerns itself with integral sum graphs, and adds \(\varsigma(G)\) isolated vertices to \(G\) instead of \(\sigma(G)\) vertices. They have computed the integral spum for the same families of graphs. While investigating spum, it is concluded that a modified concept called the sum-diameter is a more fruitful definition. The sum-diameter of a graph \(G\), denoted \(sd(G)\), considers labelings of sum graphs consisting of \(G\) along with any number of isolated vertices; while spum restricts consideration to using the minimum possible number \(\sigma(G)\) of additional isolated vertices, sum-diameter is defined identically, except without requiring the usage of exactly \(\sigma(G)\) additional isolated vertices. Similarly, the integral variant of this is called the integral sum-diameter, denoted \(isd(G)\). \(Spum(G)\) and \(ispum(G)\) are not necessarily related, but lifting the restriction of using exactly \(\sigma(G)\) or \(\varsigma(G)\) additional vertices, respectively, yields that for all graphs, \(isd(G)\leq sd(G)\). This is because expanding the set of labels from the positive integers \(\mathbb{Z}_+\) to simply the integers \(\mathbb{Z}\) should allow for a more optimal labeling, i.e., a labeling with a smaller difference between maximum and minimum label. In other words, the requirement that we first optimize the number of isolated vertices before optimizing the labeling is unnatural and impedes natural properties such as \(isd(G) \leq sd(G)\). We find that this makes bounding \(isd(G)\) far easier than \(ispum(G)\) in numerous cases. In this paper, the author provides a tight general lower bound linear in the number of vertices \(n\), as well as an asymptotically tight general upper bound quadratic in \(n\) for the sum-diameter of a graph. The author expands upon his analysis of the sum-diameter, computing certain special families of graphs and studying its behavior under various binary graph operations and vertex or edge operations. The author has also determined the spum for various families of graphs, extending the analysis by Singla et al. [loc. cit.]. In Section 2, the author formally defines the necessary concepts and provides a lemma refining the general lower bound on \(spum(G)\) computed by Singla et al. [loc. cit.]. In Section 3, the existing bounds on the spum of paths \(spum(P_n)\) have been improved. Then, in Section 4, the exact value of \(spum(C_n)\) for all cycles \(C_n\) is computed. Next, in Section 5, the existing bounds on the integral spum of cycles \(ispum(C_n)\) are improved. Then, \(spum(nK_2)\) and \(ispum(nK_2)\) are determined for all perfect matchings of \(2n\) vertices \(nK_2\). In Section 7, the notion of the sum-diameter \(sd(G)\) of a graph \(G\), as well as the integral sum-diameter \(isd(G)\) has been introduced. The author discusses basic relationships between \(spum(G), \ ispum(G), \ sd(G)\), and \(isd(G)\), generalizes the linear lower bounds computed by Singla et al. [loc. cit.] to (integral) sum-diameter, and provides a quadratic upper bound on \(sd(G)\). Then it is demonstrated that this upper bound is tight up to a constant factor, as the maximum of \(sd(G)\) among all graphs \(G\) with \(n\) vertices is \(\Omega(n^2)\). In Section 8, the previous analysis of \(spum(K_n)\) and \(ispum(K_n)\) by Singla et al. [loc. cit.] has been finetuned to exactly identify the values of \(sd(K_n)\) and \(isd(K_n)\). In Section 9, for the sum-diameter and integral sum-diameter of cycles \(C_n\) and paths \(P_n\) the bounds are obtained. In Section 10, the author provides upper bounds on the sum-diameter under various binary graph operations, in particular including the disjoint union and graph join. In Section 11, the author provides upper bounds on the sum diameter under various natural graph transformations, namely vertex addition and deletion, which extends to induced subgraphs, as well as edge addition, deletion, and contraction. There is also an open question posted concerning the monotonicity of the sum diameter with respect to induced subgraphs. In Section 12 the generalization of sum-diameter to hypergraphs has been given, and the previous general upper and lower bounds to provide preliminary bounds on both sides for arbitrary \(k\)-uniform hypergraphs are generalized. Finally, in Section 13, a conclusion is given with some remarks on areas for further research and some open questions. There are many avenues for further research regarding sum diameter. One could determine or bound the sum-diameter or integral sum-diameter for other special families of graphs. In particular, the sum-diameter for path graphs has been bounded to be either \(2n - 3\) and \(2n - 2\), and supported by computer data it is conjectured that it is the latter for all \(n \geq 7\). The spum of path graphs is similarly bounded within a constant number of options, and a computer search supports the conjecture: For \(n\geq 8\) we have \begin{align*} spum(P_n) & = \begin{cases} 2n+1 & \text{ if }n \text{ is odd}\\ 2n-1 & \text{ if }n\text{ is even} \end{cases} \end{align*} and that the current upper bound is tight for \(spum(P_n)\). An open question whether the sum-diameter is monotonic with respect to taking induced subgraphs is stated. There is a natural introduction of the integral sum-diameter in addition to the sum-diameter. But many of the bounding techniques for sum-diameter cannot immediately generalize to integral sum-diameter. Thus, the basic properties of the integral sum-diameter are still open to be studied. Lastly, the author generalized and bounded the sum-diameter of \(k\)-uniform hypergraphs. The generalization of a Sidon set, or a \(B_2\) set, to a \(B_k\) set allows anyone to upper bound the sum-diameter, but requires the \(k\)-uniform assumption. It is an open question how the study of sum-diameter can be extended to hypergraphs that are not \(k\)-uniform. It is a standard work on labeling on sum graphs. Researchers can emulate the process carried out in this paper in the work they undertake on graph labeling parameters. The paper has a tremendous amount of clarity. Researchers will be able to gain insight into graph labeling research by reading this paper.