Open access peer-reviewed chapter

# Modular Sumset Labelling of Graphs

Written By

Submitted: November 20th, 2019 Reviewed: April 29th, 2020 Published: August 8th, 2020

DOI: 10.5772/intechopen.92701

From the Edited Volume

## Number Theory and Its Applications

Edited by Cheon Seoung Ryoo

Chapter metrics overview

View Full Metrics

## Abstract

Graph labelling is an assignment of labels or weights to the vertices and/or edges of a graph. For a ground set X of integers, a sumset labelling of a graph is an injective map f:VG→PX such that the induced function f⊕:EG→PX is defined by f+uv=fu+fv, for all uv∈EG, where fu+fv is the sumset of the set-label, the vertices u and v. In this chapter, we discuss a special type of sumset labelling of a graph, called modular sumset labelling and its variations. We also discuss some interesting characteristics and structural properties of the graphs which admit these new types of graph labellings.

### Keywords

• sumset labelling
• modular sumset labelling
• weak modular sumset labelling
• strong modular sumset labelling
• arithmetic modular sumset labelling

## 1. Introduction

For terminology and results in graph theory, we refer to [1, 2, 3, 4, 5]. For further notions and concepts on graph classes, graph operations, graph products and derived graphs, refer to [3, 6, 7, 8, 9, 10]. Unless mentioned otherwise, all graphs mentioned in this chapter are simple, finite, connected and undirected.

### 1.1 Basics of graph labelling

Labelling of a graph Gcan broadly be considered as an assignment of labels or weights to the elements (vertices and edges) of Gsubject to certain pre-defined conditions. The research on graph labelling has flourished in the second half of twentieth century after the introduction of the notion of β-valuations of graphs in [11]. The β-valuationof a graph Gis an injective map f:VG1,2,3Esuch that the induced function f:EG1,2,3E, defined by fuv=fufvfor all uvEG, is also injective. Later, β-valuation of graphs was popularly known to be the graceful labellingof graphs (see [12]). Many variations of number valuations have been defined in the literature since then and most of those studies were based on the number theory and/or number theoretic properties of sets. For concepts and results in number theory, see [13, 14, 15, 16].

Analogous to the number valuations of graphs, the notion of set-labelling of graphs has been introduced in [17] as follows: Given a non-empty ground set X, a set-labellingor a set-valuationof a graph Gis an injective function f:VGPX, the power set of X, such that the induced function f:VGPXdefined by fuv=fufv, for all uvEG, where ⨁ is the symmetric difference of two sets. A graph which admits a set-labelling is called a set-labelled graphor a set-valued graph. If the induced function fis also injective, then the set-labelling fis called a set-indexer.

Subsequent to this study, many intensive investigations on set-labelling of graphs and its different types have been taken place. An overview of such studies on set-labelling of graphs can be seen in [17, 18, 19, 20, 21, 22, 23]. The study on set-labelling has been extended by replacing the binary operation ⨁ by some other binary operations of sets. For example, two different types of set-labellings—called disjunctive set-labelling and conjunctive set-labelling—of graphs have been studied in [24]. These set-labellings are defined respectively in terms of the union and the intersection of two sets instead of the symmetric difference of two sets.

### 1.2 Sumsets and integer additive set-labelled graphs

Integer additive set-labelling or sumset labelling of graphs has been a new addition to the theory of set-labelling of graphs recently. The notion of sumsets of two sets is explained as follows: Let Aand Bbe two sets of numbers. The sumsetof Aand Bis denoted by A+Band is defined by A+B=a+b:aAbB(see [25]). Remember that a sumset of two sets can be determined if and only if both of them are number sets. If either Aor Bis countably infinite, then their sumset A+Bis also a countably infinite set and if any one of them is a null set, then the sumset is also a null set. If Cis the sumset of two sets Aand B, then both Aand Bare said to be the summandsof C.

We note that A+0=Aand hence Aand 0are called the trivial summands of the set A. Also, note that A+Bneed not be a subset or a super set of Aand/or B. But, AA+Bif 0B. Furthermore, the sumset of two subsets of a set Xneed not be a subset of the ground set X. These observations are clear deviations from the other common binary operations of sets and thus the study of sumsets becomes more interesting. For the terms, concepts and results on sumsets, we refer to [25, 26, 27, 28, 29, 30, 31, 32, 33, 34].

Note that if Aand Bare two non-empty finite sets of integers, then A+B1A+BA×B=AB(see [25]). The exact cardinality of the sumset A+Balways depends on the number as well as the pattern of elements in both the summands Aand B. The counting procedure in this case is explained in [35] as follows: Two ordered pairs aband cdin A×Bis said to be compatibleif a+b=c+d. If aband cdare compatible, then it is written as abcd. It can easily be verified that this relation is an equivalence relation. A compatibility classof an ordered pair abin A×Bwith respect to the integer k=a+bis the subset of A×Bdefined by cdA×B:abcdand is denoted by abkor Ck. The cardinality of a compatibility class in A×Blies between 1 and minAB. Note that the sum of coordinates of all elements in a compatibility class is the same and this sum will be an element of the sumset A+B. That is, the cardinality of the sumset of two sets is equal to the number of equivalence classes on the Cartesian product of the two sets generated by the compatibility relation defined on it.

Using the concepts of the sumsets of sets, the notion of integer additive set-labelling of graphs has been introduced in [36] as follows: Let Xbe a set of non-negative integers and P0Xbe the collection of the non-empty subsets of X. Then, an integer additive set-labellingor an integer additive set-valuationof a graph Gis an injective map f:VGPXsuch that the induced function f:EGPXis defined by f+uv=fu+fv, for all uvEG, where fu+fvis the sumset of the set-label the vertices uand v(see [36, 37]). A graph with an integer additive set-labelling is called an integer additive set-labelled graph. It can very easily be verified that every graph Gadmits an integer additive set-labelling, provided the ground set Xis chosen judiciously.

Following to the above path-breaking study, the structural properties and characteristics of different types of integer additive set-labellings of graphs are studied intensively in accordance with the cardinality of the set-label, nature and pattern of elements in the set-label, nature of the collection of set-label, etc. Some interesting and significant studies in this area can be found in [35, 36, 37, 38, 39, 40, 41, 42, 43, 44]. Later, the studies in this area have been extended by including the sets of integers (including negative integers also) for labelling the elements of a graph. Some extensive studies in this area, can be seen in [45, 46].

As a specialisation of the sumset labelling of graphs, the notion of modular sumset labelling of graphs and corresponding results are discussed in the following section.

## 2. Modular sumset labelling of graphs

### 2.1 Basics of modular sumsets

Recall that Zndenotes the set of integers modulo n, where nis a positive integer. The modular sumsetof two subsets Aand Bof Znis the set k:aAbBa+bkmodn. Unless mentioned otherwise, throughout this chapter, the notation A+Bdenotes the modular sumset of the sets Aand B. Unlike the ordinary sumsets, the modular sumset A+BZnif and only if A,BZn. This fact will ease many restrictions imposed on the vertex set-label of a sumset graph Gin order to ensure that the edge set-label are also subsets of the ground set.

If we assign the null set Øto any vertex as the set-label, the set-label of every edge incident at that vertex will also be a null set. To avoid such an embarrassing situation, we do not consider the null set for labelling any vertex of graphs. Thus, the set of all non-empty subsets of a set Xis denoted by P0X. That is, P0X=PX\0.

### 2.2 Modular sumset graphs

In view of the facts stated above, the modular sumset labelling of a graph is defined as follows:

Definition 2.1.[47] A modular sumset labelling of a graph Gis an injective function f:VGP0Znsuch that the induced function f+:EGP0Znis defined as f+uv=fu+fv, where fu+fvis the modular sumset of the set labels of the vertices uand v. A graph which admits a modular sumset labelling is called a modular sumset graph.

Definition 2.2.[47] A modular sumset labelling of a graph Gis said to be a uniform modular sumset labellingof Gif the set-label of all its edges have the same cardinality. A modular sumset labelling fof Gis said to be a k-uniform modular sumset labellingif f+uv=k,uvEG.

Proposition 2.1.[47] Every graphGadmits modular sumset labelling (for a suitable choice ofn).

The proof of the above proposition is immediate from the fact that fu+fvZnif and only if fu,fvZn.

An immediate question that arises in this context is about the minimum size of the ground set Zn(that is, the minimum value of n) required for the existence of a modular sumset labelling of G.

As in the case of sumsets, the cardinality of the modular sumsets also attracted the attention. Hence, we have the bounds for the cardinality of an edge set-label of a modular sumset graph Gis as follows:

Theorem 2.2.[47] Letf:VGP0Znbe a modular sumset labelling of a given graphG. Then, for any edgeuvEG, we have

fu+fv1f+uv=fu+fvfufvn.E1

The theorem follows immediately from the theorem on the cardinality of sumsets (see Theorem 2.7, p. 52, [25]).

In this context, it is quite interesting to investigate whether the bounds are sharp. It has also been proved in [25] that the lower bound is sharp when both fuand fvare arithmetic progressions (we call set an arithmetic progression if its elements are in arithmetic progression) with the same common difference. We shall discuss the different types of modular sumset graphs based on the set-labelling numbers of its vertices and edges, one by one in the coming discussions.

## 3. Arithmetic modular sumset graphs

As mentioned above, the lower bound of the inequality (1) is sharp if both summand set-label are arithmetic progressions with the same common difference. If the context is clear, the common difference of the set-label (if exists) of an element may be called the common differenceof that element. The deterministic ratioof an edge of Gis the ratio, k1between the common differences of its end vertices. In view of this terminology we have the following definition.

Definition 3.1.For any vertex vof G, if fvis an arithmetic progression, then the modular sumset labelling f:VGP0Znis called a vertex arithmetic modular sumset labellingof G. In a similar manner, for any edge eof G, if feis an arithmetic progression, then the modular sumset labelling f:EGP0Znis called an edge arithmetic modular sumset labellingof G.

The difference set of a non-empty set A, denoted by DA, is the set defined by DA=ab:abA. Note that if Ais an arithmetic progression, then its difference set DAis also an arithmetic progression and vice versa. Analogous to the corresponding result of the edge-arithmetic sumset labelling of graphs (see [44, 46]), the following result is a necessary and sufficient condition for a graph Gto be edge-arithmetic modular sumset graph in terms of the difference sets the set-label of vertices of G.

Theorem 3.1.Letfbe a modular sumset labelling defined on a graphG. If the set-label of an edge ofGis an arithmetic progression if and only if the sumset of the difference sets of set-label of its end vertices is an arithmetic progression.

Proof.Let f:VGP0be a modular sumset labelling defined on G. Let ai,ajbe two arbitrary elements in fuand let br,bsbe two elements in fv. Then, aiajDfuand aiajDfu. That is, Dfu=aiaj:aiajfuand Dfv=brbs:brbsfv.

Now, assume that f+e=f+uvis an arithmetic progression for an edge e=uvEG. That is, A=fu+fvis an arithmetic progression. Then, the difference set DA=ab:abA=fu+fvis also an arithmetic progression. Since a,bA, we have a=ai+brand b=aj+bs, where ai,ajfuand br,bsfv. Then,

DA=ab:abA=ai+braj+bs:aiajfubrbsfv=aiaj+brbs:aiajfubrbsfv=aiaj:aiajfu+brbs:brbsfv=Dfu+Dfv

Hence, Dfu+Dfvis an arithmetic progression.

Conversely, assume that Dfu+Dfvis an arithmetic progression. Then, by previous step, we have Dfu+Dfv=DA, where A=fu+fv. Then, we have DAis an arithmetic progression. Since the difference set DAis an arithmetic progression, then by the above remark, we have A=fu+fv=f+uvis also an arithmetic progression. Hence, the edge e=uvhas an arithmetic progression as its set-label. □

In view of the notions mentioned above, we note that there are some graphs, all whose elements have arithmetic progressions as their set-label and there are some graphs, the set-label of whose edges are not arithmetic progressions. Keeping this in mind, we define the following notion.

Definition 3.2.An arithmetic sumset labellingof a graph Gis a modular sumset labelling fof G, with respect to which the set-label of all vertices and edges of Gare arithmetic progressions. A graph that admits an arithmetic modular sumset labelling is called an arithmetic modular sumset graph.

Analogous to the condition for an arithmetic sumset graphs (see [44]), a necessary and sufficient condition for a graph to admit an arithmetic modular sumset labelling is discussed in the following theorem.

Theorem 3.2.A graph G admits an arithmetic modular sumset labelling f if and only if for any two adjacent vertices in G, the deterministic ratio of every edge of G is a positive integer, which is less than or equal to the set-labelling number of its end vertex having smaller common difference.

Proof.Here, we need to consider the following two cases:

Case 1: First note that if the set-label of two adjacent vertices are arithmetic progressions with the same common difference, say d, then the set-label of the corresponding edge is also an arithmetic progression with the same common difference d. Then, it is clear that a vertex arithmetic modular sumset graph is an arithmetic modular sumset graph if the common differences between any two adjacent vertices of Gare the same.

Case 2: Assume that u,vbe any two adjacent vertices in Gwith common differences duand dvrespectively such that dudv. Also, assume that fu=ar=a+rdu:0r<mand fv=bs=b+sdv:0s<n. Then, fu=mand fv=n. Now, arrange the terms of fu+fv=f+uvin rows and columns as follows. For any bsfv,0s<n, arrange the terms of A+bsin s+1th row in such a way that equal terms of different rows come in the same column of this arrangement. Without loss of generality, assume that dv=kduand km. If k<m, then for any afuand bfvwe have a+b+dv=a+b+kdu<a+b+mdi. That is, a few final elements of each row of the above arrangement occur as the initial elements of the succeeding row (or rows) and the difference between two successive elements in each row is duitself. If k=m, then the difference between the final element of each row and the first element of the next row is duand the difference between two consecutive elements in each row is du. Hence, if km, then f+uvis an arithmetic progression with common difference du.

In both cases, note that if the given conditions are true, then fis an arithmetic modular sumset labelling of G.

We prove the converse part by contradiction method. For this, assume that fis an arithmetic modular sumset labelling of G. Let us proceed by considering the following two cases.

Case-1:Assume that djis not a multiple of di(or diis not a multiple of dj). Without loss generality, let di<dj. Then, by division algorithm, dj=pdi+q,0<q<di. Then, the differences between any two consecutive terms in f+vivjare not equal. Hence, in this case also, fis not an arithmetic modular sumset labelling, contradiction to the hypothesis. Therefore, didj.

Case 2:Let dj=kdiwhere k>m. Then, the difference between two successive elements in each row is di, but the difference between the final element of each row and the first element of the next row is tdi, where t=km+11. Hence, fis not an arithmetic modular sumset labelling, a contradiction to the hypothesis. Hence, we have dj=kdi;km.

Therefore, from the above cases it can be noted that if a vertex arithmetic modular sumset labelling of Gis an arithmetic modular sumset labelling of G, then the deterministic ratio of every edge of Gis a positive integer, which is greater than or equal to the set-labelling number of its end vertex having smaller common difference. This completes the proof. □

In the following theorem, we establish a relation between the common differences of the elements of an arithmetic modular sumset graph G.

Theorem 3.3.If G is an arithmetic modular sumset graph, the greatest common divisor of the common differences of vertices of G and the greatest common divisor of the common differences of the edges of G are equal to the smallest among the common differences of the vertices of G.

Proof.Let fbe an arithmetic modular sumset labelling of G. Then, by Theorem 3.2, for any two adjacent vertices viand vjof Gwith common differences diand djrespectively, either di=dj, or if dj>di,dj=kdj, where kis a positive integer such that 1<kfvi.

If the common differences of the elements of Gare the same, the result is obvious. Hence, assume that for any two adjacent vertices viand vjof G, dj=kdj,kfvi, where diis the smallest among the common differences of the vertices of G. If vris another vertex that is adjacent to vj, then it has the common difference drwhich is equal to either dior djor ldj. In all the three cases, dris a multiple of di. Hence, the greatest common divisor of di,dj,dris di. Proceeding like this, we have the greatest common divisor of the common differences of the vertices of Gis di.

Also, by Theorem 3.2, the edge uivjhas the common difference di. The edge vjvkhas the common difference di, if dk=di, or djin the other two cases. Proceeding like this, we observe that the greatest common divisor of the common differences of the edges of Gis also di. This completes the proof.□

The study on the set-labelling number of edges of an arithmetic modular sumset graphs arouses much interest. Analogous to the result on set-labelling number of the edges of an arithmetic sumset graph (see [43]), The set-labelling number of an edge of an arithmetic modular sumset graph G, in terms of the set-labelling numbers of its end vertices, is determined in the following theorem.

Theorem 3.4.Let G be a graph which admits an arithmetic modular sumset labelling, say f and letdianddjbe the common differences of two adjacent verticesviandvjin G. Iffvifvj, then for some positive integer1kfvi, the edgevivjhas the set-labelling numberfvi+kfvj1.

Proof.Let fbe an arithmetic modular sumset labelling defined on G. For any two vertices viand vjof G, let fvi=aiai+diai+2diai+3diai+m1diand let fvj=ajaj+djaj+2djaj+3djaj+n1dj. Here fvi=mand fvj=n.

Let diand djbe the common differences of the vertices viand vjrespectively, such that di<dj. Since fis an arithmetic modular sumset labelling on G, by Theorem 3.2, there exists a positive integer ksuch that dj=k.di, where 1kfvi. Then, fvj=ajaj+kdiaj+2kdiaj+3kdiaj+n1kdi. Therefore, f+vivj=ai+ajai+aj+diai+aj+2diai+aj+m1+kn1di. That is, the set-labelling number of the edge vivjis m+kn1. □

## 4. Strongly modular sumset graphs

The next type of a modular sumset labelling we are going to discuss is the one with the upper bound in Inequality (1) is sharp (that is, A+B=AB). Thus, we have the following definition.

Definition 4.1.[47] A modular sumset labelling f:VGP0Zndefined on a given graph Gis said to be a strongly modular sumset labellingif for the associated function f+:EGP0Zn, f+uv=fufvuvEG. A graph which admits a strongly modular sumset labelling is called a strongly modular sumset graph.

Invoking the notion difference set of a set, a necessary and sufficient condition of a modular sumset labelling of a graph Gto be a strongly modular sumset labelling is given below:

Theorem 4.1.A modular sumset labellingf:VGP0Znof a given graph G is a strongly modular sumset labelling of G if and only ifDfuDfv=Ø,uvEG, wherefufvn.

Proof.Let f:VGP0Znbe a modular sumset labelling on a given graph G. For any vertex uVG, define Dfu=aiaj:aiajfu.

Let uvbe an arbitrary edge in EG. Assume that fis a strong modular sumset labelling of G. Then, by definition f+uv=fufv. Therefore, for any elements ai,ajfuand br,bsfv, we have ai+braj+bsin f+uvuvEG. That is, aiajbsbrfor any ai,ajfuand br,bsfv. That is, DfuDfv=Ø. Therefore, the difference sets of the set-label of any two adjacent vertices are disjoint.

Conversely, assume that the difference DfuDfv=Øfor any edge uvin G. That is, aiajbsbrfor any ai,ajfuand br,bsfv. Then, aiajbsbr. That is, ai+braj+bs. Therefore, all elements in fu+fvare distinct. That is, f+uv=fufvfor any edge uvEG. Hence, fis a strongly modular sumset labelling of G.

Also, note that the maximum possible cardinality in the set-label of any element of Gis n, the product fufvcannot exceed the number n. This completes the proof. □

A necessary and sufficient condition for a modular sumset labelling of a graph Gto be a strongly k-uniform modular sumset labelling is given below:

Theorem 4.2.[47] For a positive integerkn, a modular sumset labellingf:VGP0Znof a given connected graph G is a stronglyk-uniform modular sumset labelling of G if and only if eitherkis a perfect square or G is bipartite.

Proof.If kis a perfect square, say k=l2, then we can label all the vertices of a graph by distinct l-element sets in such a way that the difference sets of the set-label of every pair of adjacent vertices are disjoint. Hence, assume that kis not a perfect square.

Let Gbe a bipartite graph with bipartition XY. Let r,sbe two divisors of k. Label all vertices of Xby distinct r-element sets all of whose difference sets are the same, say DX. Similarly, label all vertices of Yby distinct s-element sets all of whose difference sets the same, say DY, such that DXDY=Ø. Then, all the edges of Ghave the set-labelling number k=rs. Therefore, Gis a strongly k-uniform modular sumset graph.

Conversely, assume that Gadmits a strongly k-uniform modular sumset labelling, say f. Then, f+uv=kuvEG. Since, fis a strong modular sumset labelling, the set-labelling number of every vertex of Gis a divisor of the set-labelling numbers of the edges incident on that vertex. Let vbe a vertex of Gwith the set-labelling number r, where ris a divisor of k, but r2k. Since fis k-uniform, all the vertices in Nv, must have the set-labelling number s, where rs=k. Again, all vertices, which are adjacent to the vertices of Nv, must have the set-labelling number r. Since Gis a connected graph, all vertices of Ghave the set-labelling number ror s. Let Xbe the set of all vertices of Ghaving the set-labelling number rand Ybe the set of all vertices of Ghaving the set-labelling number s. Since r2k, no two elements in X(and no elements in Yalso) can be adjacent to each other. Therefore, Gis bipartite.□

The following result is an immediate consequence of the above theorem.

Theorem 4.3.[47] For a positive non-square integerkn, a modular sumset labellingf:VGP0Znof an arbitrary graph G is a stronglyk-uniform modular sumset labelling of G if and only if either G is bipartite or a disjoint union of bipartite components.

For a positive integer kn, the maximum number of components in a strongly k-uniform modular sumset graph is as follows.

Proposition 4.4.[47] Let f be a stronglyk-uniform modular sumset labelling of a graph G with respect to the ground setZn. Then, the maximum number of components in G is the number of distinct pairs of divisorsrandsofksuch thatrs=k.

The following theorem discusses the condition for an arithmetic modular sumset labelling of a graph Gto be a strongly modular sumset labelling of the graph.

Theorem 4.5.LetGbe a graph which admits an arithmetic modular sumset labelling, sayf. Then,fis a strongly modular sumset labelling ofGif and only if the deterministic ratio of every edge ofGis equal to the set-labelling number of its end vertex having smaller common difference.

Proof.Let fbe an arithmetic modular sumset labelling of G. Let viand vjare two adjacent vertices in Gand diand djbe their common differences under f. Without loss of generality, let di<dj. Then, by Theorem 3.4, the set-labelling number of the edge vivjis fvi+kfvj1.

Assume that fis a strongly modular sumset labelling. Therefore, f+vivj=mn. Then,

fvi+kfvj1=fvifvjkfvj1=fvifvj1k=fvi.

Conversely, assume that the common differences diand djof two adjacent vertices viand vjrespectively in G, where di<djsuch that dj=fvi.di. Assume that fvi=ar=a+rdi:0r<fviand fvj=bs=b+skdi:0s<fvj, where kfvi. Now, arrange the terms of f+vivj=fvi+fvjin rows and columns as follows. For bsfvj,0s<fvj, arrange the terms of fvi+bsin s+1-th row in such a way that equal terms of different rows come in the same column of this arrangement. Then, the common difference between consecutive elements in each row is di. Since k=fvi, the difference between the final element of any row (other than the last row) and first element of its succeeding row is also di. That is, no column in this arrangement contains more than one element. Hence, all elements in this arrangement are distinct. Therefore, total number of elements in fvi+fvjis fvifvj. Hence, fis a strongly modular sumset labelling.□

## 5. Supreme modular sumset labelling of G

In both types of modular sumset labelling discussed above, it is observed that the cardinality of the edge set-label cannot exceed the value n. This fact creates much interest in investigating the case where all the edge set-label have the cardinality n.

Definition 5.1.[47] A modular sumset labelling f:VGP0Znof a given graph Gis said to be a supreme modular sumset labellingor maximal modular sumset labellingof Gif and only if f+EG=Zn.

Put in a different way, a modular sumset labelling f:VGPZnof a given graph Gis a supreme modular sumset labelling of Gif the set-label of every edge of Gis the ground set Znitself.

A necessary and sufficient condition for a modular sumset labelling of a graph Gto be its supreme modular sumset labelling is discussed in the theorem given below:

Theorem 5.1.[47] The modular sumset labellingf:VGPZnof a given graphGis a supreme modular sumset labelling ofGif and only if for every pair of adjacent verticesuandvofGsome or all of the following conditions hold.

1. fu+fvnif DfuDfvØ. The strict inequality hold when Dfuand Dfvare arithmetic progressions containing the same elements.

2. fufvnif DfuDfv=Ø.

Proof.For two adjacent vertices uand vin G, let Dfu=Dfv=dare arithmetic progressions containing the same elements. Then, the elements in fuand fvare also in arithmetic progression, with the same common difference d. Then, by Theorem 3.4, n=fu+fv=fu+fv1. Therefore, the set-labelling number of the edge uvis nif and only if fu+fv>n.

Now, let DfuDfvØsuch that DfuDfv. Then, clearly fu+fvfu+fv. Therefore, we have f+uv=nif and only if fu+fvn.□

Next assume that DfuDfv=Ø. Then, fu+fv=fufv. Therefore, we have f+uv=nif and only if fufvn.

A necessary and sufficient condition for a strong modular sumset labelling of a graph Gto be a maximal modular sumset labelling of G.

Theorem 5.2.[47] Letfbe a strong sumset-labelling of a given graphG. Then,fis a maximal sumset-labelling ofGif and only ifnis a perfect square orGis bipartite or a disjoint union of bipartite components.

Proof.The proof is an immediate consequence of Theorem 4.2, when k=n.□

## 6. Weakly modular sumset graphs

Another interesting question we address in the beginning of this section is whether the lower bound and the upper bound of the sumset can be equal. Suppose that Aand Bbe two non-empty subsets of Znsuch that the bounds of their sumset are equal. Then, we have

A+B1=ABA+B1AB=0A1B+B1=0A1B1=0

which is possible only when A=1or B=1(or both). Also, note that in this case the cardinality of the sumset is equal to equal to that of one of the summands. This interesting phenomenon leads us to a new type of a modular sumset labelling called weakly modular sumset labelling. This type of labelling is investigated in the following section.

### 6.1 Weakly modular sumset labelling of graphs

Definition 6.1.A modular sumset labelling fof a graph Gis said to be a weakly modular sumset labellingof Gif the cardinality of the set-label of every edge of Gis equal to the cardinality of the set-label of at least one of its end vertices. A graph which admits a weakly modular sumset labelling is called a weakly modular sumset graph.

From the above definition, it can be observed that for any edge uvin weakly modular sumset graph G, f+uv=fuor f+uv=fv. Putting it in a different way, the set-labelling number of at least one end vertex of every edge of a weakly modular sumset graph is a singleton. An element (a vertex or an edge) of modular sumset graph Gwith set-labelling number 1is called a sparing elementor a monocardinal elementsof G. Hence, analogous to the condition for a sumset graph to be a weak sumset graph (see [39]), we have.

Theorem 6.1.A graphGadmits a weak modular sumset labelling if and only ifGis bipartite or contains sparing edges.

Proof.Note the fact that at least one end vertex of every edge of Gis a sparing vertex. Also, we note that no two vertices with non-singleton set-label in weakly modular sumset graph can be adjacent to each other. Thus, if every of edge of Ghas exactly one end vertex with singleton set-label, then we can partition the vertex set of Ginto two subsets Xwith all sparing vertices and Ywith all non-sparing vertices. Here, no two vertices in the same partition are adjacent and hence Gis a bipartite graph. If Gis not a bipartite graph, then obviously Gshould have at least one sparing edge, completing the proof.

Invoking Theorem 6.1, the following two results are immediate.

Corollary 6.2.Every graphGadmits a weakly modular sumset labelling.

Corollary 6.3.A graphGadmits a weakly uniform modular sumset labelling if and only ifGis bipartite.

The above results are similar to the corresponding result of integer additive set-labelled graphs (see [39]) and hence the notion of sparing numberof graphs defined and studied in [48, 49, 50, 51, 52, 53, 54, 55, 56, 57] can be extended to our current discussion also. The notion of the sparing number of graphs is defined as follows:

Definition 6.2.Let Gbe a weakly modular sumset labelled graph. Then, the sparing numberof Gis the number of sparing edges in G.

A set of vertices Xof a graph Gis said to have maximal incidence if the maximum number of edges of incidence at the elements of X. Then, analogous to the corresponding result of integer additive set-valued graphs (see [40]), we have.

Theorem 6.4.LetGbe a weakly modular sumset labelled graph andIbeIbe the largest independent set ofGwith maximum incidence. Then, the sparing number ofGisEGviIdvi.

Proof.Recall that the degree of a vertex v, denoted by dv, is equal to the number of edges incident on a vertex. Note that any vertex viIcan have a non-singleton set-label which gives non-singleton set labels to dviedges incident on it. Since Iis an independent set, the edges incident at the vertices in Iassumes non-singleton set-label. Therefore, the number of edges having non-singleton set-label incident at the vertices in Iis viIdvi. Since Iis a maximal independent set of that kind, the above expression counts the maximal non-sparing edges in G. Hence, the number of sparing edges in Gis EGviIdvi. □

### 6.2 Weakly modular sumset number of graphs

As a special case of the modular sumset number, the notion of weakly modular sumset number is introduced in [47] as follows:

Definition 6.3.The weakly modular sumset numberof a graph G, denoted by σwis defined to be the minimum value of nsuch that a modular sumset labelling f:VGP0Znis a weakly modular sumset labelling of G.

The following theorem discussed the weak sumset number of an arbitrary graph Gin terms of its covering and independence numbers.

Theorem 6.5.[47] LetGbe a modular sumset graph andαandβbe the covering number and independence number ofGrespectively. Then, the weak modular sumset number ofGismaxαr, whereris the smallest positive integer such that2rr1β.

Proof.Recall that αG+βG=VG(see [4]). Since Gis a modular sumset graph, no two adjacent vertices can have non-singleton set-label simultaneously. Therefore, the maximum number of vertices that have non-singleton set-label is β. Let Vbe the set of these independent vertices in G. Therefore, the minimum number of sparing vertices is VGβ=α. Since all these vertices in VVmust have distinct singleton set-label, the ground set must have at least αelements.

Also, the number non-empty, non-singleton subsets of the ground set must be greater than or equal to α. Otherwise, all the vertices in Vcannot be labelled by non-singleton subsets of this ground set. We know that the number of non-empty, non-singleton subsets of a set Ais 2AA1, where AZnis the ground set used for labelling.

Therefore, the weak modular sumset number Gis αif 2αα1β. Otherwise, the ground set must have at least relements such that 2rr1β. Therefore, in this case, the weak modular sumset number of Gis r, where ris the smallest positive integer such that 2rr1β. Hence, σG=maxαr. This completes the proof.□

The weakly modular sumset number some fundamental graph classes are given in Table 1.

Graph classσ*(G)
Path, Pp2 if p2; p2if p>2
Cycle, Cpp1if p=3,4; p2if p>4
Wheel graph, W1,p1 + p2
Helm graph, Hpp
Complete graph, Kpp1

### Table 1.

Weakly modular sumset number of some graph classes.

The following theorem discusses the minimum cardinality of the ground set when the given graph Gadmits a weakly uniform modular sumset labelling.

Theorem 6.6.[47] LetGbe a weaklyk-uniform modular sumset graph with covering numberαand independence numberβ, wherek<α. Then, the minimum cardinality of the ground setZnismaxαr, where r is the smallest positive integer such thatrkβ.

Proof.Let a weakly k-uniform modular sumset labelling be defined on a graph Gover the ground set AZn. Then, by Corollary 6.3, Gis bipartite. Let X,Ybe the bipartition of the vertex set VG. Without loss of generality, let XY. Then, α=Xand β=Y. Then, distinct elements of Xmust have distinct singleton set-label. Therefore, nα.

On the other hand, since fis k-uniform, all the elements in Ymust have distinct k-element set-label. The number of k-element subsets of a set A(obviously, with more than kelements) is Ak. The ground set Ahas αelements only if αkβ. Otherwise, the ground set Amust contain at least relements, where r>αis the smallest positive integer such that rkβ. Therefore, n=maxαr.□

In view of the above theorem, the following result is immediate.

Corollary 6.7.LetGbe a weaklyk-uniform modular sumset graph, wherekα, whereαis the covering number ofG. Then, the minimum cardinality of the ground setZnis the smallest positive integernsuch thatnkβ, whereβis the independence number ofG.

The following result explains a necessary and sufficient condition for a weak modular sumset labelling of a given graph Gto be a maximal modular sumset labelling of G.

Proposition 6.8.[47] A weakly modular sumset labelling of a graphGis a supreme modular sumset labelling ofGif and only ifGis a star graph.

Proof.Let fbe a weak modular sumset labelling of given graph G. First, assume that fis a maximal modular sumset labelling of G. Then, the set-labelling number of one end vertex of every edge of Gis 1and the set-labelling number of the other end vertex is n. Therefore, Znbe the set-label of one end vertex of every edge of G, which is possible only if Gis a star graph with the central vertex has the set-label Znand the pendant vertices of Ghave distinct singleton set-label.

Conversely, assume that Gis a star graph. Label the central vertex of Gby the ground set Znand label other vertices of Gby distinct singleton subsets of Zn. Then, all the edges of Ghas the set-labelling number n. That is, this labelling is a supreme modular sumset labelling of G.□

## 7. Conclusion

In this chapter, we have discussed certain types of modular sumset graphs and their structural properties and characterisations. These studies are based on the cardinality of the set-label of the elements of the graphs concerned and the patterns of the elements in these set-label. It is to be noted that several other possibilities can be investigated in this regard. For example, analogous to the topological set-valuations of graphs, the case when the collection of set-label of vertices and/or edges of a graph Gforms a topology of the ground set Zncan be studied in detail. Another possibility for future investigation is to extend the graceful and sequential concepts of set-labelling of graphs to modular sumset labelling also. All these points highlight the wide scope for further studies in this area.

## Acknowledgments

The author would like to dedicate the chapter to his doctoral thesis supervisor Prof. Dr. Germina K Augusthy for her constant support and inspiration for working in the area of sumset-labelling. The author would also like to acknowledge the critical and creative suggestions of the editor and referees which improved the content and the presentation style of the chapter.

Mathematics Subject Classification 2010: 05C75

## References

1. 1. Bondy JA, Murty USR. Graph Theory with Applications. Vol. 290. London: Macmillan; 1976
2. 2. Bondy JA, Murty USR. Graph Theory. New York: Springer; 2008
3. 3. Gross JL, Yellen J, Zhang P. Handbook of Graph Theory. Boca Raton: Chapman and Hall/CRC; 2013
4. 4. Harary F. Graph Theory. New Delhi: Narosa Publ. House; 2001
5. 5. West DB. Introduction to Graph Theory. Vol. 2. Upper Saddle River: Prentice Hall; 2001
6. 6. Bača M, MacDougall J, Miller M, Wallis W. Survey of certain valuations of graphs. Discussiones Mathematicae Graph Theory. 2000;20(2):219-229
8. 8. Gallian JA. A dynamic survey of graph labeling. Electronic Journal of Combinatorics 1 (Dynamic Surveys). 2018:DS6
9. 9. Hammack R, Imrich W, Klavžar S. Handbook of Product Graphs. Bocca Raton: CRC Press; 2011
10. 10. Imrich W, Klavzar S. Product Graphs: Structure and Recognition. New York: Wiley; 2000
11. 11. Rosa A. On certain valuations of the vertices of a graph. In: Theory of Graphs International Symposium; July; Rome. 1966. pp. 349-355
12. 12. Golomb SW. How to number a graph. In: Graph Theory and Computing. Cambridge, UK: Academic Press; 1972. pp. 23-37
13. 13. Apostol TM. Introduction to Analytic Number Theory. New Delhi: Narosa Publ. House; 2013
14. 14. Burton DM. Elementary Number Theory. Noida, India: Tata McGraw-Hill Education; 2006
15. 15. Cohn H. Advanced Number Theory. N Chelmford: Courier Corporation; 2012
16. 16. Nathanson MB. Elementary Methods in Number Theory. Vol. 195. New York: Springer Science & Business Media; 2008
17. 17. Acharya BD. Set valuations of a graph and their applications. In: MRI Lecture Notes in Applied Mathematics, 2. Allahabad: Mehta Research Instt; 1986
18. 18. Acharya BD. Set-indexers of a graph and set-graceful graphs. Bulletin of the Allahabad Mathematical Society. 2001;16:1-23
19. 19. Acharya BD, Germina KA. Set-valuations of graphs and their applications: A survey. Annals of Pure and Applied Mathematics. 2013;4(1):8-42
20. 20. Acharya BD, Hegde SM. On certain vertex valuations of a graph I. Indian Journal of Pure and Applied Mathematics. 1991;22(7):553-560
21. 21. Acharya BD, Rao SB, Arumugam S. Embeddings and NP-complete problems for graceful graphs. In: Labeling of Discrete Structures and Applications. New Delhi: Narosa Pub. House; 2008. pp. 57-62
22. 22. Augusthy GK. Set-valuations of graphs and their applications. In: Handbook of Research on Advanced Applications of Graph Theory in Modern Society. Hershey, Pennsylvania: IGI Global; 2020. pp. 171-207
23. 23. Germina KA. Set-valuations of graphs and their applications. Final Technical Report. Vol. 4. DST Grant-in-Aid Project No. SR/S4/277/05
24. 24. Naduvath S. On disjunctive and conjunctive set-labelings of graphs. Southeast Asian Bulletin of Mathematics. 2019;43(4):593-600
25. 25. Nathanson MB. Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Vol. 165. New York: Springer Science & Business Media; 1996
26. 26. Nathanson MB. Sums of finite sets of integers. American Mathematical Monthly. 1972;79(9):1010-1012
27. 27. Nathanson MB. Additive Number Theory: The Classical Bases. Vol. 164. New York: Springer Science & Business Media; 2013
28. 28. Nathanson MB. Problems in Additive Number Theory. I. In Additive Combinatorics. Vol. 43. Providence, RI: American Mathematical Society; 2007. pp. 263-270
29. 29. Ruzsa IZ. Generalized arithmetical progressions and sumsets. Acta Mathematica Hungarica. 1994;65(4):379-388
30. 30. Ruzsa IZ. Sumsets and structure. In: Combinatorial Number Theory and Additive Group Theory. 2009. pp. 87-210
31. 31. Sudev NK, Germina KA, Chithra KP. Weak integer additive set-labeled graphs: A creative review. Asian-European Journal of Mathematics. 2015;8(3):1550052
32. 32. Sudev NK, Germina KA, Chithra KP. Strong integer additive set-valued graphs: A creative review. International Journal of Computer Applications. 2015;97(5):8887
33. 33. Sudev NK, Germina KA, Chithra KP. Arithmetic integer additive set-valued graphs: A creative review. The Journal of Mathematics and Computer Science. 2020;10(4):1020-1049
34. 34. Tao T. Sumset and inverse sumset theory for Shannon entropy. Combinatorics, Probability and Computing. 2010;19(4):603-639
35. 35. Sudev NK, Germina KA. On integer additive set-indexers of graphs. International Journal of Mathematical Sciences and Engineering Applications. 2015;7(01):1450065
36. 36. Germina KA, Sudev NK. On weakly uniform integer additive set-indexers of graphs. International Mathematical Forum. 2013;8(37):1837-1845
37. 37. Germina KA, Anandavally TMK. Integer additive set-indexers of a graph: Sum square graphs. Journal of Combinatorics, Information & System Sciences. 2012;37(2-4):345-358
38. 38. Sudev NK. Set valuations of discrete structures and their applications [PhD thesis]. Kannur University; 2015
39. 39. Naduvath S, Germina K. A characterisation of weak integer additive set-indexers of graphs. Journal of Fuzzy Set Valued Analysis. 2014, 2014;1jfsva-00189
40. 40. Sudev NK, Germina KA, Chithra KP. Weak set-labeling number of certain integer additive set-labeled graphs. International Journal of Computers and Applications. 2015;114(2):1-6
41. 41. Sudev NK, Germina KA. On weak integer additive set-indexers of certain graph classes. Journal of Discrete Mathematical Sciences & Cryptography. 2015;18(1–2):117-128
42. 42. Sudev NK, Germina KA. Some new results on strong integer additive set-indexers of graphs. Discrete Mathematics, Algorithms and Applications. 2015;7(01):1450065
43. 43. Sudev NK, Germina KA. On certain arithmetic integer additive set-indexers of graphs. Discrete Mathematics, Algorithms and Applications. 2015;7(03):1550025
44. 44. Sudev NK, Germina KA. A study on arithmetic integer additive set-indexers of graphs. Journal of Informatics and Mathematical Sciences. 2018;10(1–2):321-332
45. 45. Naduvath S, Augusthy GK, Kok J. Sumset valuations of graphs and their applications. In: Handbook of Research on Advanced Applications of Graph Theory in Modern Society. Hershey, Pennsylvania: IGI Global; 2020. pp. 208-250
46. 46. Naduvath S, Germina KA. An Introduction to Sumset Valued Graphs. Mauritius: Lambert Academic Publ; 2018
47. 47. Naduvath S. A study on the modular sumset labeling of graphs. Discrete Mathematics, Algorithms and Applications. 2017;9(03):1750039
48. 48. Chithra KP, Sudev NK, Germina KA. Sparing number of Cartesian products of certain graphs. Communications in Mathematics and Applications. 2014;5(1):23-30
49. 49. Chithra KP, Sudev NK, Germina KA. A study on the sparing number of corona of certain graphs. Research & Reviews: Discrete Mathematical Structures. 2014;1(2):5-15
50. 50. Naduvath S, Kaithavalappil C, Augustine G. A note on the sparing number of generalised petersen graphs. Journal of Combinatorics, Information & System Sciences. 2017;42(1–2):23-31
51. 51. Sudev NK, Germina KA. A note on the sparing number of graphs. Advances and Applications in Discrete Mathematics. 2014;14(1):51-65
52. 52. Sudev NK, Germina KA. On the sparing number of certain graph structures. Annals of Pure and Applied Mathematics. 2014;6(2):140-149
53. 53. Sudev NK, Germina KA. Further studies on the sparing number of graphs. TechS Vidya e-Journal of Research. 2014;2(2):25-36
54. 54. Sudev NK, Germina KA. A note on the sparing number on the sieve graphs of certain graphs. Applied Mathematics E-Notes. 2015;15(1):29-37
55. 55. Sudev NK, Germina KA. Some new results on weak integer additive set-labeled graphs. International Journal of Computers and Applications. 2015;128(1):1-5
56. 56. Sudev NK, Chithra KP, Germina KA. Sparing number of the certain graph powers. Acta Universitatis Sapientiae Mathematica. 2019;11(1):186-202
57. 57. Sudev NK, Chithra KP, Germina KA. Sparing number of the powers of certain Mycielski graphs. Algebra and Discrete Mathematics. 2019;28(2):291-307

Written By