The Sum Graph And The Integral Sum Graph

From a practical point of view, sum graph labeling can be used as acompressed representation of a graph, a data structure for representingthe graph. Data compression is important not only for saving memory spacebut also for speeding up some graph algorithms when adapted to work withthe compressed representation of the input graph.The concept of sum graph was introduced by F. Harary in 1990.. LetG = (V (G),E(G)) be a graph, where V = V (G) and E = E (G) denote thevertex set and the edge set of G respectively. Let N (Z) denote the setof all positive integers (integers) .The sum graph G⁺(S ) of a finitesubset 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 a (an integral) sum graph if it is isomorphicto the sum graph of some S (?)N(Z).The (integral) sum numberσ = σ(G)(ζ = ζ(G))of G is the smallest number of isolated verticeswhich when added to G result in a (an integral) sum graph, i.e.σ = σ(G )=min{s:(?)S(?)N,such that G ∪ sK₁ ≌G⁺(S),ands ≥0} (ζ = ζ(G )=min{s:(?)S(?)Z,such that G ∪ sK₁ ≌G⁺(S),and s ≥0}). Itis obviously that ζ (G )≤ σ(G) for any graphG .To better understand the notions of the sum graph and the integralsum graph, some authors give us the definitions of the (integral) sumlabeling. A (An integral) labeling of graphG is a one-one mapping L:V (G )→ N(Z).A (An integral) labeling L of G is called a (an integral)sum labeling if for every pair of distinct vertices u and v ofG , uv ∈ E(G) if and only if there exists w∈ V(G)with L (u )+ L(v)=L(w).For convenience, throughout this paper we may assume that the verticesof G are identified with their labels.Since F. Harary presented the concept of sum graph in 1990,theresearch work has been aimed at determining the sum number, integral sumnumber of some graph classes. Up to now the (mod, integral) sum numbersof some popular graphs such as completegraphs K n,cycles C n,paths Pn ,bipartite graphs K m, n, wheels W n, fans Fn andcocktail party graphs H 2 ,n have been obtained, but the researches to theproperty of the sum graph and the integral sum graph have been ignored.The first chapter of this paper gives us a brief introduction aboutthe basic concepts, terminologies and symbols which are used in this paper.In the second chapter the properties of integral sum graphs are discussed.In the third chapter we determine the sum numbers of graph G n, nandK n , n? E( nK2) respectively and define a new graph L n and bound its sumnumber. A new kind of exclusive graphs is also defined. In the last chapterwe determine a new kind of integral sum trees by identification.In this paper we have the following theorems.Theorem 2.1 For n ≥4, integral sum graph G has at most two noteswith n ?1degrees;G has two notes with n ?1degrees if and only ifG ? G+ ( ?1,0,1,2,,n?2).Theorem 2.2 For n ≥4,(1)If δ (G)≥???n2 ???+1,then G is not an integral sum graph;the bound isbest possible.(2)Let σ 2?min{s + s′:s≠s′∈S,ss′?E},if σ 2 ≥ 2???n2???+2, then G is not aintegral sum graph;the bound is best possible.Theorem 2.3 For n ≥4, ? (G )≤n?2,(1) If δ (G)≥???n2 ???+1, then G is not a integral sum graph;the bound isbest possible;(2)If 2σ 2 ≥ 2???n2???+, then G is not an integral sum graph.Theorem 3.1For n ≥5, σ ( K n , n?E(nK2) = 2 n ?3.Theorem 3.2.1 For n ≥3, σ (G n, n)= 2n+1.Theorem 3.3.3 2 n ≤ σ (Pn, n)≤2n+2Theorem 3.4.3 For n ≥3, 2 ≤ σ (Ln)≤3.Theorem 3.5 For n ≥5, C n, n is exclusive.Theorem 4.2 Trees with all forks at least distance 2 apart and everyfork contains a path with length 2 are integral sum graphs.