Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 404 https://internationalpubls.com Every Tree is an Integral Sum Graph S. Muthukkumar, K. Rajendran Vels Institute of Science Technology and Advanced Studies Chennai, India muthumed77@gmail.com, gkrajendra59@gmail.com Article History: Received: 26-02-2024 Revised: 25-04-2024 Accepted: 10-05-2024 Abstract: A finite simple graph G is called an integral sum graph (respectively, sum graph) if there is a bijection f from the vertices of G to a set of integers S (respectively, a set of positive integers S) such that uv is an edge of G if and only if f (u)+f (v) ∈ S. In 1999, Liaw et al (Ars Comb., Vol.54, 259-268) posed the conjecture that every tree is an integral sum graph. In this note, we prove that all trees are integral sum graphs. Further, we prove that every bipartite graph is an induced subgraph of a sum graph G with sum number σ(G) = 1. Keywords: Integral sum graphs; sum graphs; integral sum number; 1. Introduction All the graphs considered in this paper are finite simple graphs. Terms that are not defined here can be referred from the book [10]. Sum Graphs and Integral Sum Graphs were introduced by Harary [5]. A graph G is called a sum graph if the vertices of G can be labeled with distinct positive integers so that e = uv is an edge of G if and only if the sum of the labels of the vertex u and vertex v is also a label in G. It is clear that if G is a properly labeled sum graph, then the vertex receiving the highest label cannot be adjacent to any other vertex. Thus, every sum graph must contain isolated vertices. In other words, a connected graph is not a sum graph. If G is not a sum graph, adding a finite number of isolated vertices to it always yields a sum graph. Given any graph G with p vertices and q edges, it is trivial that the union G ∪ qK1 of G with q isolated vertices is a sum graph. We can define the sum number σ(G) of G as the smallest number (say s) of isolated vertices added to G such that G ∪ sK1 is a sum graph. An integral sum graph is also defined just as the sum graph, difference being that the label set S is a subset of Z, the set of integers. The integral sum number ζ(G) is the smallest non-negative integer s such that G ∪ sK1 is an integral sum graph. Clearly for any graph G, ζ(G) ≤ σ(G). For a survey on sum graphs and integral sum graphs, we refer to the dynamic survey on graph labeling by Gallian [4]. Liaw et al [7] posed the conjecture that every tree is an integral sum graph. This conjecture was proved only for some classes of trees: caterpillars, banana trees, generalized stars and trees whose forks (by fork we mean a vertex of degree not 2) are distance at least 4 from each other [1, 2]. He et al [6] reduced this distance to 3. Pyatkin [8] proved that every tree whose forks are at least distance 2 apart is an Integral Sum Graph. Also, Pyatkin proved that subdivided trees are integral sum graphs. Ellingham [3] proved that σ(T ) = 1 for every T≠K1. Tiwari and Tripathi [9] gave some bounds on the number of edges for a graph to be sum graphs and integral sum graphs. In this paper, we prove that all trees are integral sum graphs. That is, we prove that conjecture posed by Liaw et al [7] is true. Further, we prove a characterization result that every bipartite graph is an induced subgraph of a sum graph G with sum number σ(G) = 1. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 405 https://internationalpubls.com 2. Trees are Integral sum graphs In this section, we prove our main result that all trees are integral sum graphs. Theorem 1. Every tree T with n vertices is an integral sum graph. Proof. Let T be an arbitrary tree with n vertices. Since trees are bipartite, consider the bipartition of vertex set of T as V(T) = V1 ∪ V2. Without loss of generality, let |V1| ≥ |V2|. Let |V1| = k and |V2| = r. Consider the vertices in V1 as V1 = {u1, u2, · · · , uk}and V2 as V2 = {v1, v2, · · · , vr}. Label the vertices of tree T as follows: f (ui) = i − 1 for 1 ≤ i ≤ k and f (vi) = −i for 1 ≤ i ≤ r. By the definition of function f, the vertex labels of vertices in V1 are from the set {0, 1, 2, · · ·, k − 1} and the vertex labels of vertices in V2 are from the set {−1, −2, · · ·, −r}. Therefore, it is clear that f is a bijection from the set of vertices of T to a subset of integers. The edge label of an arbitrary edge e = uv defined by f (e) = f (u) + f (v). It is enough that if we prove that there exists a vertex in T whose vertex label is f (u) + f (v). Let us assume the contrary that exists an edge label f (e) = f (u) + f (v) but there does not exist a vertex whose label is f (e). Therefore, by our assumption f (u) + f (v) ≥ k or f (u) + f (v) < −r. Since e = uv and T is bipartite, one end vertex of the edge e = uv is in V1 and the other end vertex is in V2. Without loss of generality, let us assume that u ∈ V1 and v ∈ V2. Therefore, f (u) ∈ {0, 1, 2, · · ·, k − 1} and f (v) ∈ {−1, −2, · · ·, −r} Case 1: |f (u)| ≥ |f (v)| Since f (v) ∈ {−1, −2, · · ·, −r}, implies that f (u) + f (v) ≥ 0 and f (u)+f (v) < f (u). This implies that f (u)+f (v) lies in the set {0, 1, · · ·, f (u)−|f (v)|}, a contradiction to our assumption that f (u)+f (v) ≥ k since |f (v)| ≥ 1 and f (u)−|f (v)| < k. Therefore, in this case, our assumption that there does not exist a vertex whose vertex label is f (e) = f (u) + f (v) is wrong. Case 2: |f (u)| ≤ |f (v)| Since f (v) ∈ {−1, −2, · · ·, −r}, implies that f (u) + f (v) ≤ 0 and f (u) + f (v) > f (v). This implies that f (u) + f (v) lies in the set {0, −1, · · ·, f (u) + f (v)}, a contradiction to our assumption that f (u) + f (v) < −r since |f (u)| ≥ 0. Therefore, in this case, our assumption that there does not exist a vertex whose vertex label is f (e) = f (u) + f (v) is wrong. Therefore, there exists a vertex in T whose vertex label is f (u) + f (v). This proves that the labeling function f satisfies the conditions of integral sum graphs. Therefore, tree T is an integral sum graph. 2.1 Illustrative example For the arbitrary tree T in Figure 1, the bipartition of the vertex set of T is shown in Figure 2 and its integral sum labeling is shown in Figure 3. Figure 1: Tree T with 23 edges Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 406 https://internationalpubls.com Figure 2: Bipartition of the vertex set of tree T 0 1 2 3 −1 4 −2 5 −3 6 −4 7 −5 8 −6 9 −7 10 −8 11 −9 12 13 14 Figure 3: Integral sum labeling for tree T 3 Characterization of Sum Graphs In this section, we prove that any bipartite graph is an induced subgraph of a sum graph Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 407 https://internationalpubls.com G with sum number σ(G) = 1. Theorem 2. Let B = (V1, V2) be any bipartite graph with |V1| ≥ |V2|. Then there exists a sum graph G with σ(G) = 1 such that B is an induced subgraph of G. Proof. Given that B = (V1, V2) is a bipartite graph with |V1| ≥ |V2|. Let |V1| = r and |V2| = s. Consider the vertices in V1 as {u1, u2, · · ·, ur} and the vertices in V2 as {v1, v2, · · ·, vs}. Define the vertex labeling function f as f (ui) = 2i − 1, for 1 ≤ i ≤ r and f (vi) = 2i, for 1 ≤ i ≤ s. By the definition of f, it is clear that f is one-to- one. Now, define the edge label for an edge e = uv as f (e) = f (u) + f (v). Since B is a bipartite graph, every edge in B has one end in V1 and the other end in V2, and being all the vertex labels of vertices in V1 are odd whereas vertex labels of vertices in V2 are even, by the definition of the edge labels, the edge label of any edge in B is an odd number. Define Vf = {the set of all vertex labels of vertices of B} and Ef = {the set of all edge labels of edges of B}. Let L = E − (Vf ∩ Ef ) = {x1, x2, · · · , xt} and let z be the maximum label among the labels in L. Now, let us construct the bipartite graph G as follows: Start with the bipartite graph B along with their labels as defined by the function f. Add an isolated vertex with label z. Define L′ = L − {z}. Until L′ = ϕ, choose a label (say y) from L′, add a vertex with vertex label y to the vertex with vertex label z − y and remove the label y from the set L′. Observe that by the construction of graph G, G is a sum graph with one isolated vertex. Therefore, σ(G) = 1. Thus, we have constructed a sum graph G with σ(G) = 1in such a way that given bipartite graph B is an induced subgraph of G. Hence the proof. 3.1 Illustrative Example For the bipartite graph in Figure 4, the corresponding sum graph G with σ(G) = 1 is shown in Figure 5. Figure 4: Bipartite Graph B(V1, V2) 1 15 2 3 13 4 5 11 6 7 8 9 17 Figure 5: Sum Graph G with bipartite graph B as an induced subgraph Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 408 https://internationalpubls.com 4 Conclusion In this note, we proved that all trees are integral sum graphs. Further, we proved a characterization result that any bipartite graph is an induced subgraph of a sum graph G with σ(G) = 1. We have given a constructive procedure on to generate such sum graphs G for a given bipartite graph. References [1] Z. Chen, Integral sum graphs from identification, Disc. Math., 181, (1998), 77-90. [2] Z. Chen, On integral sum graphs, Disc. Math., 306, (2006), 19-25. [3] M.N. Ellingham, Sum graphs from trees, Ars Comb., 35, (1993), 335-349. [4] Gallian J.A., A Dynamic Survey of Graph Labeling, The Electronic Journal of Com- binatorics, 22nd Edition, (2019), #DS6. [5] F. Harary, Sum graphs over all integers, Disc. Math., 124, (1994), 99-105. [6] W. He, L. Wang, H. Mi, Y. Shen, X. Yu, Integral sum graphs from a class of tree, Ars Combin., LXX, (2004). [7] S.C. Liaw, D. Kuo, G. Chang, Integral sum numbers of graphs, Ars Combin., 54, (1999), 259-268. [8] A.V. Pyatkin, Subdivided trees are integral sum graphs, Disc. Math., 308, (2008), 1749-1750. [9] A. Tiwari and A. Tripathi, On the range of size of sum graphs and integral sum graphs of a given order, Disc. Appl. Math., 161, (2013), 2653-2661. [10] West D.B., Introduction to Graph Theory, Prentice Hall of India, 2nd Edition, 2001.