Open access peer-reviewed chapter - ONLINE FIRST

Modular Sumset Labelling of Graphs

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

DOI: 10.5772/intechopen.92701

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 MSC 2010: 05C75

1. Introduction

For terminology and results in graph theory, we refer to [9, 10, 21, 23, 57]. For further notions and concepts on graph classes, graph operations, graph products and derived graphs, refer to [8, 11, 16, 21, 22, 24]. 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 G can broadly be considered as an assignment of labels or weights to the elements (vertices and edges) of G subject 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 [35]. The β-valuation of a graph G is 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 labelling of graphs (see [20]). 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 [7, 12, 15, 34].

Analogous to the number valuations of graphs, the notion of set-labelling of graphs has been introduced in [1] as follows: Given a non-empty ground set X, a set-labelling or a set-valuation of a graph G is 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 graph or a set-valued graph. If the induced function fis also injective, then the set-labelling f is 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 [1, 2, 3, 4, 5, 6, 17]. 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 [25]. 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 A and B be two sets of numbers. The sumset of A and B is denoted by A+Band is defined by A+B=a+b:aAbB(see [31]). Remember that a sumset of two sets can be determined if and only if both of them are number sets. If either A or B is 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 C is the sumset of two sets A and B, then both A and B are said to be the summands of C.

We note that A+0=Aand hence A and 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 X need 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 [30, 31, 32, 33, 36, 37, 46, 47, 48, 56].

Note that if A and B are two non-empty finite sets of integers, then A+B1A+BA×B=AB(see [31]). The exact cardinality of the sumset A+Balways depends on the number as well as the pattern of elements in both the summands A and B. The counting procedure in this case is explained in [39] as follows: Two ordered pairs aband cdin A×Bis said to be compatible if 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 class of 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 [19] as follows: Let X be a set of non-negative integers and P0Xbe the collection of the non-empty subsets of X. Then, an integer additive set-labelling or an integer additive set-valuation of a graph G is 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 [18, 19]). 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 G admits an integer additive set-labelling, provided the ground set X is 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 [18, 19, 38, 39, 40, 41, 42, 43, 44, 45]. 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 [27, 28].

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 sumset of two subsets A and B of Znis the set k:aAbBa+bkmodn. Unless mentioned otherwise, throughout this chapter, the notation A+Bdenotes the modular sumset of the sets A and 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 G in 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 X is 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. [26] A modular sumset labelling of a graph G is 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. [26] A modular sumset labelling of a graph Gis said to be a uniform modular sumset labelling of 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 labelling if f+uv=k,uvEG.

Proposition 2.1. [26] Every graph Gadmits modular sumset labelling (for a suitable choice of n).

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. [26] Let f:VGP0Znbe a modular sumset labelling of a given graph G. Then, for any edge uvEG, 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, [31]).

In this context, it is quite interesting to investigate whether the bounds are sharp. It has also been proved in [31] 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 difference of that element. The deterministic ratio of 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 labelling of 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 labelling of 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 [28, 45]), 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. Let fbe a modular sumset labelling defined on a graph G. If the set-label of an edge of Gis 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 labelling of a graph G is a modular sumset labelling f of G, with respect to which the set-label of all vertices and edges of G are 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 [45]), 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 G are the same.

Case 2: Assume that u,vbe any two adjacent vertices in G with 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 f is an arithmetic modular sumset labelling of G.

We prove the converse part by contradiction method. For this, assume that f is 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, f is 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, f is 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 G is an arithmetic modular sumset labelling of G, then the deterministic ratio of every edge of G is 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 f be an arithmetic modular sumset labelling of G. Then, by Theorem 3.2, for any two adjacent vertices viand vjof G with 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 G are 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 G is 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 G is 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 [44]), 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 let diand djbe the common differences of two adjacent vertices viand vjin G. If fvifvj, then for some positive integer 1kfvi, the edge vivjhas the set-labelling number fvi+kfvj1.

Proof. Let f be 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 f is 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. [26] A modular sumset labelling f:VGP0Zndefined on a given graph G is said to be a strongly modular sumset labelling if 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 G to be a strongly modular sumset labelling is given below:

Theorem 4.1. A modular sumset labelling f:VGP0Znof a given graph G is a strongly modular sumset labelling of G if and only if DfuDfv=Ø,uvEG, where fufvn.

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 f is 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, f is a strongly modular sumset labelling of G.

Also, note that the maximum possible cardinality in the set-label of any element of G is 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 G to be a strongly k-uniform modular sumset labelling is given below:

Theorem 4.2. [26] For a positive integer kn, a modular sumset labelling f:VGP0Znof a given connected graph G is a strongly k-uniform modular sumset labelling of G if and only if either kis 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 G be 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 G have the set-labelling number k=rs. Therefore, G is a strongly k-uniform modular sumset graph.

Conversely, assume that G admits a strongly k-uniform modular sumset labelling, say f. Then, f+uv=kuvEG. Since, f is a strong modular sumset labelling, the set-labelling number of every vertex of G is a divisor of the set-labelling numbers of the edges incident on that vertex. Let vbe a vertex of G with the set-labelling number r, where ris a divisor of k, but r2k. Since f is 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 G is a connected graph, all vertices of G have the set-labelling number ror s. Let Xbe the set of all vertices of G having the set-labelling number rand Ybe the set of all vertices of G having the set-labelling number s. Since r2k, no two elements in X (and no elements in Y also) can be adjacent to each other. Therefore, G is bipartite.□

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

Theorem 4.3. [26] For a positive non-square integer kn, a modular sumset labelling f:VGP0Znof an arbitrary graph G is a strongly k-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. [26] Let f be a strongly k-uniform modular sumset labelling of a graph G with respect to the ground set Zn. Then, the maximum number of components in G is the number of distinct pairs of divisors rand sof ksuch that rs=k.

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

Theorem 4.5. Let Gbe a graph which admits an arithmetic modular sumset labelling, say f. Then, fis a strongly modular sumset labelling of Gif and only if the deterministic ratio of every edge of Gis 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. [26] A modular sumset labelling f:VGP0Znof a given graph G is said to be a supreme modular sumset labelling or maximal modular sumset labelling of G if 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. [26] The modular sumset labelling f:VGPZnof a given graph Gis a supreme modular sumset labelling of Gif and only if for every pair of adjacent vertices uand vof Gsome 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. [26] Let fbe a strong sumset-labelling of a given graph G. Then, fis a maximal sumset-labelling of Gif and only if nis a perfect square or Gis 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 labelling of 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 element or a monocardinal elements of G. Hence, analogous to the condition for a sumset graph to be a weak sumset graph (see [40]), we have.

Theorem 6.1. A graph Gadmits a weak modular sumset labelling if and only if Gis 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 graph Gadmits a weakly modular sumset labelling.

Corollary 6.3. A graph Gadmits a weakly uniform modular sumset labelling if and only if Gis bipartite.

The above results are similar to the corresponding result of integer additive set-labelled graphs (see [40]) and hence the notion of sparing number of graphs defined and studied in [13, 14, 29, 49, 50, 51, 52, 53, 54, 55] 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 number of 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 [41]), we have.

Theorem 6.4. Let Gbe a weakly modular sumset labelled graph and Ibe Ibe the largest independent set of Gwith maximum incidence. Then, the sparing number of Gis EGviIdvi.

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 [26] as follows:

Definition 6.3. The weakly modular sumset number of 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. [26] Let Gbe a modular sumset graph and αand βbe the covering number and independence number of Grespectively. Then, the weak modular sumset number of Gis maxαr, where ris the smallest positive integer such that 2rr1β.

Proof. Recall that αG+βG=VG(see [23]). 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. [26] Let Gbe a weakly k-uniform modular sumset graph with covering number αand independence number β, where k<α. Then, the minimum cardinality of the ground set Znis maxαr, where r is the smallest positive integer such that rkβ.

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. Let Gbe a weakly k-uniform modular sumset graph, where kα, where αis the covering number of G. Then, the minimum cardinality of the ground set Znis the smallest positive integer nsuch that nkβ, where βis the independence number of G.

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. [26] A weakly modular sumset labelling of a graph Gis a supreme modular sumset labelling of Gif and only if Gis 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 G forms 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.

How to cite and reference

Cite this chapter Copy to clipboard

Sudev Naduvath (August 8th 2020). Modular Sumset Labelling of Graphs [Online First], IntechOpen, DOI: 10.5772/intechopen.92701. Available from:

More statistics for editors and authors

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

View all Books