Lower Integral Sum Graph And Exclusive Lower Integral Sum Graph

Harary[2] presented the concept of sum graph in 1990. Harary[3] 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 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 said that S is one of the (integral) sum labeling,and we consider the vertices and labelings as the same.The (integral) sum number σ(G)(ζ(G)) is the smallest number of isolated vertices which when added to G resulted in an (integral) sum graph.The concept of the mod sum graph was introduced by Boland[4] 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[5] presented the concept of mod sum number. The mod sum number ρ(G) of G is the least number p of isolated vertices ρK₁ such that G ∪ ρK₁ is a mod sum graph.Miller[6] presented the concept of Exclusive graph in 2003. A sum labeling S is called an exclusive sum labeling , if u + v ∈ S\V(G) for any edge uv E E(G). The exclusive sum number ε(G) of G is the least number e of isolated vertices εK₁ such that G∪εK₁ is an exclusive sum graph.Dou[7] presented the concept of Mod integral sum graph in 2004. A mod integral sum graph is a sum graph with S (?) Z_m and all arithmetic performed modulo m where m ≥ |S|. The mod integral sum number ψ(G) of G is the least number ψ of isolated vertices ψK₁ such that G∪ψK₁ is a mod integral sum graph.From a practical point of view, sum graph labelling can be used as a compressed representation of a graph, a data structure for representing the graph.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 the input graph.New concepts are presented in this thesis as follows:Let [x\ denote the largest integer which is not larger than the real x,Q* denote the set of all the positive reals.The lower integral sum graph G+(S) of a nonempty finite subset S C Q* is the graph (S, E) with uv e E if and only if [n + vj E S. A graph G is said to be an lower integral sum graph if it is isomorphic to the lower integral sum graph of some S C Q*. The lower integral sum number a' (G)) is the smallest number of isolated vertices which when added to G resulted in a lower integral sum graph.A vertice w is called a working vertice,if there exists an edge uv with w =[u + v\.Suppose that S is the lower integral sum labeling of G,and all integral vertices are working vertices,then we say that S is a standard lower integral sum labeling.A lower integral sum labeling S is called an exclusive lower integral sum labeling ,if [u + v\ e S\V(G) for any edge uv G E(G).Lower integral sum labeling and exclusive lower integral sum labeling are another ways used as compressed representation of a graph.The first chapter of this thesis gives a brief introduction about the basic concepts,terminologies and symboles of (lower integral )sum graph.In the second chapter we give some properties of (exclusive) lower integral sum graph .In the third chapter,we determine (exclusive) lower integral sum number of some graphs ,and give a method of determining the lower integral sum number of certain graph. In the fouth chapter,we discuss the (exclusive) lower integral sum properties of some graphs.At last, in the fifth chapter we advance the things to be discussed . In this thesis we obtain the following results.Theorem 2.5 Suppose that G is a nonempty lower integral sum graph , thena).There exist no vertices Vi,v2,v3,V4 satisfying [uj = [v4\, [t?2J = [vs e E.b).There exist no vertices Vi(l < i < 5),satisfying 0 < Vi — v5 < 1(1 < i <4), [U5 + W1J = [v5 + V4\,V5V1,V5V4,V1V3,V2V4 ï¿¡ E,VXV2lV3V4 g E.c).There exist no vertices Uj(l < i < 6),satisfying [vi\ = k(l < i < 3), vxv4, v2v4,VlV5,V3V5,V2V6,V3V6 6 E,V3V4,V2V5,ViV6 g E.d).There exist no vertices u,(l < i < 6),satisfying |_t>ij k(l < i < 3), 1^4,E.e).There exist no vertices u,-(l < i < 6),satisfying [vi\ = k(l < i < 3), V1V4, v2v4,E.f).There exist no vertices Vi(l < i < 6),satisfying [vi\ = k{\ < i < 3), v3v4, v2v5, e E, vxv4, v2v4, ViV5, v3v5, v2v6, v3v6 (ï¿¡ E.Theorem 2.6 Suppose that G is a lower integral sum graph ,5 is a lower integral sum labeling, and max(S - [S\) < |, k > 0, k 6 Z,then k[S\ + S is also a lower integral sum labeling of G.Theorem 2.7 There are no isolate vertices in G\,G2, Si is the lower integral sum labeling of Gi U v'{Gi)Ki,a (Gi) > l,and max(Si — [5jJ) < |, Cj is the set of working vertices(i = 1, 2),and there exist a vertice m ï¿¡-C2,n = maxC\, (m,n) — l,then a'iGr \JG2) < a {G^ + a {G2) - 1.Theorem 2.8 There are no isolate vertices in G, S — S\ \}S2 is the lower integral sum labeling of G\]o'(G)Ki,in which Si is the labeling of G,S2 is the labeling of isolate vertices, and mm(51-[51J) >\,k>O,k€ Z,thenk([S\+l)+S is also a lower integral sum labeling of G{]o (G)K\.Theorem 2.9 For any lower integral sum graph G,V(G) — {u,|0 < i < n - l},suppose voVi G E(l < i < 4),Viv2,v3v4 G E, Viv3,viv4, v2v4 ï¿¡ ^^hen the number of working vertices of G is more than 1.Theorem 2.10 Theorem 2.13 obtain thatFor any lower integral sum graph G, suppose that there exists C5, Cq, K2;2>2 or P6 as the induced subgraph of (?,then,the number of working vertices of G is more than 1.§3.1 obtain mK2,Kn,KrtS,Kn - E(Kr)(r < n),Kn\JKr^,Kltniq are lower integral sum graphs.The lower integral sum number of Kmtniq(m,n, q > 2) is 2.The lower integral sum numbers of C5, C5 \JKn are 1.§3.2 obtain the exclusive lower integral sum number of mK2, Kn, Kr,s, Kn U A"rs, Kn — E(Kr)(l < r < n — l),KiiTltq is l.The exclusive lower integral sum number of Km,nfq{m, n, q > 2) is 2.§3.3 gives us a method of determining the lower integral sum number of graphs.We determine the lower integral sum number of Km,n,q(m, n, q > 2), KT:S with this method .This method can help us construct many kinds of lower integral sum graphs according to one kind of lower integral sum graphs,and determine the boundary of the lower integral sum number of one kind of graphs according to another kind of graphs.We need the definition of symmetrical vertices and Theorem 3.3.1.Vi, Vj are called two symmetrical vertices of G,if for any vertices Vk ^ Vi, Vj of G,satisfing ViVk € E(G) if and only if VjVk G E(G).Theorem 3.3.1 Suppose Vi,v2 are two symmetrical vertices of G,G\ = G + vxv2 (If vxv2 € ï¿¡(G),then Gx = G), G2 = G - u^If vxv2 i ï¿¡?(G),then G2 = G),then min(a'(Gi),only if 1 < m < 5.§4.2 discuss that with what condionds the exclusive lower integral sum number of graphs Fn(n > 2), Wn(n > 3), Kr>s - E(mK2){r, s > m), Kn - E(mK2)(2 < 2m < n),Kn — E(Pm)(n > m) is 1. Following are the results:Theorem 4.2.1 e'(Fn) = l(n > 2) if and only if n = 2 or 3. Theorem 4.2.2 e'(Wn) = l(n > 3) if and only if n = 3.Theorem 4.2.3 e'{Kr m,r, s > 2) if and. only if m — 1 or 2.Theorem 4.2.4 e (Kn - E(mK2)) = 1(2 < 2m < n, n ^ 2) if and only if m=l or 2.Theorem 4.2.5 e (Kn - E{Pm)) = \{n > m,n,m ^[WJflt^j l,2,3)if and only if m — 1,2,3 or n = m = 4,5.