Some Results On (Lower) Integral Sum Graphs

All graphs considered in this paper are finite, simple and undirected. In general, we follow the graph-theoretical notation and terminology of [1].Harary presented the concept of sum graph in 1990. Harary presented the concept of integral sum graph in 1994. Let N(Z) denote the set of all positive integers (integers). The (integral) sum graph G⁺(S) of a nonempty finite subset S(?)N(Z) is the graph (S, E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S(?)N(Z). We say that S is an (integral) sum labelling of G, and we consider a vertex and its labelling as the same. The (integral) sum numberσ(G)(ζ(G)) is the smallest number of isolated vertices which when added to G result in an (integral) sum graph.The concept of rood sum graph was introduced by Boland etal in 1990. A mod sum graph is a sum graph with S(?)Z_m\{0} and all arithmetic performed modulo m where m≥|S|+1. Then, Sutton etal presented the concept of rood sum number. The rood sum numberρ(G) of G is the least number n of isolated vertices nK₁ such that G∪nK₁ is a mod sum graph.In 2006, Li and Gao introduced the concept of lower integral sum graph. Let Q^* denote the set of all positive rational numbers, the lower integral sum graph G₊(S) of a finite subset S(?)Q^* is the graph (S, E) with uv∈E if and only if [u+v]∈S. A graph G is said to be a lower integral sum graph if it is isomorphic to the lower integral sum graph of some S(?)Q^*. We say that S is a lower integral sum labelling of G, and we consider a vertex and its labelling as the same. The lower integral sum numberσ'(G) is the smallest number of isolated vertices which when added to G resulted in a lower integral sum graph.From a practical point of view, sum labellings can be used as a compressed representation of a graph by computer. Data compression is important not only for saving memory space but also for speeding up some graph algorithms when adapted to work with the compressed representation of input graphs.Now the research aims at two aspects. One is to study the relation between the (mod, integral, lower integral) sum numbers and other parameters, the structures of the graph. The other is at determining the sum number, integral sum number, rood sum number and lower integral sum number of some graph classes. So far, some achievements have been gotton, some good methods and general theorems have been gotton and extended to hypergraphs.The first chapter of this paper gives a brief introduction about the basic concepts, terminologies and symboles, and some important conclusions of sum graph which are used in this paper; In the second chapter we discuss a family of integral sum graphs from identification; In the third chapter we determine the lower integral sum numbers of even cycles, balloon, wheel (*)-graph and fan (*)-graph; In the fourth chapter, we discuss the lower integral sum numbers of disjoint union of complete bipartite graphs and complete tripartite graphs.In this paper we obtain the following theorems:Theorem 2.1 Let Go is a (*)-sum graph with respect to r₀, P(a, b) is a spine of a caterpillar T, then (G₀, r₀)∞(T, a) is a (*)-sum graph with respect to a leaf of b. Particularly, (G₀, r₀)∞(T, a) is an integral sum graph. Theorem 2.2 Let (G, r)=(G₀, r₀)∞(G', r') and GO is a (*)-sum graph with respect to to, (G', r')=(G'(n₁, n+2,…, n_t), r') is a generalized star, where n_i is the number of the paths with length i and t is the largest i such that n_i＞0, then G is an integral sum graph.Theorem 3.1.3 Except C₄ which is a lower integral sum graph, the lower integral sum number of even cycle C_2n is 1.Theorem 3.2.1 Balloon C_{n, 2} is a lower integral sum graph for all n≥4 and n is even.Theorem 3.3.4 W_n,m is a lower integral sum graph for all n≥3, m≥2.Theorem 3.3.6 F_n,m is a lower integral sum graph for all m≥1.Theorem 4.1.3 K_n1,m1∪K_{n2, m2}∪…∪K_{nr, mr} is a lower integral sum graph.Theorem 4.2.3 The lower integral sum number of K_{m, n, p}∪K_{r, s, l} is 2 for all m, n, p, r, s, l≥2.Theorem 4.2.4 K_{1, m, n}∪K_{r, s, l} is a lower integral sum graph for all n≥4.