Open access peer-reviewed chapter

Modular Sumset Labelling of Graphs

Written By

Sudev Naduvath

Submitted: 20 November 2019 Reviewed: 29 April 2020 Published: 08 August 2020

DOI: 10.5772/intechopen.92701

From the Edited Volume

Number Theory and Its Applications

Edited by Cheon Seoung Ryoo

Chapter metrics overview

608 Chapter Downloads

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 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 [11]. The β-valuation of a graph G is an injective map f:VG1,2,3E such that the induced function f:EG1,2,3E, defined by fuv=fufv for all uvEG, is also injective. Later, β-valuation of graphs was popularly known to be the graceful labelling of 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-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:VGPX defined 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 f is 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 [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 A and B be two sets of numbers. The sumset of A and B is denoted by A+B and 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 A or B is countably infinite, then their sumset A+B is 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=A and hence A and 0 are called the trivial summands of the set A. Also, note that A+B need not be a subset or a super set of A and/or B. But, AA+B if 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 [25, 26, 27, 28, 29, 30, 31, 32, 33, 34].

Note that if A and B are two non-empty finite sets of integers, then A+B1A+BA×B=AB (see [25]). The exact cardinality of the sumset A+B always 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 [35] as follows: Two ordered pairs ab and cd in A×B is said to be compatible if a+b=c+d. If ab and cd are 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 ab in A×B with respect to the integer k=a+b is the subset of A×B defined by cdA×B:abcd and is denoted by abk or Ck. The cardinality of a compatibility class in A×B lies 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 X be a set of non-negative integers and P0X be 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:VGPX such that the induced function f:EGPX is defined by f+uv=fu+fv, for all uvEG, where fu+fv is the sumset of the set-label the vertices u and 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 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 [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.

Advertisement

2. Modular sumset labelling of graphs

2.1 Basics of modular sumsets

Recall that Zn denotes the set of integers modulo n, where n is a positive integer. The modular sumset of two subsets A and B of Zn is the set k:aAbBa+bkmodn. Unless mentioned otherwise, throughout this chapter, the notation A+B denotes the modular sumset of the sets A and B. Unlike the ordinary sumsets, the modular sumset A+BZn if 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. [47] A modular sumset labelling of a graph G is an injective function f:VGP0Zn such that the induced function f+:EGP0Zn is defined as f+uv=fu+fv, where fu+fv is the modular sumset of the set labels of the vertices u and 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 G is said to be a uniform modular sumset labelling of G if the set-label of all its edges have the same cardinality. A modular sumset labelling f of G is said to be a k-uniform modular sumset labelling if f+uv=k,uvEG.

Proposition 2.1. [47] Every graph G admits modular sumset labelling (for a suitable choice of n).

The proof of the above proposition is immediate from the fact that fu+fvZn if 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 G is as follows:

Theorem 2.2. [47] Let f:VGP0Zn be 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, [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 fu and fv are 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.

Advertisement

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 G is the ratio, k1 between the common differences of its end vertices. In view of this terminology we have the following definition.

Definition 3.1. For any vertex v of G, if fv is an arithmetic progression, then the modular sumset labelling f:VGP0Zn is called a vertex arithmetic modular sumset labelling of G. In a similar manner, for any edge e of G, if fe is an arithmetic progression, then the modular sumset labelling f:EGP0Zn is 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 A is an arithmetic progression, then its difference set DA is 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 G to be edge-arithmetic modular sumset graph in terms of the difference sets the set-label of vertices of G.

Theorem 3.1. Let f be a modular sumset labelling defined on a graph G. If the set-label of an edge of G is 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:VGP0 be a modular sumset labelling defined on G. Let ai,aj be two arbitrary elements in fu and let br,bs be two elements in fv. Then, aiajDfu and aiajDfu. That is, Dfu=aiaj:aiajfu and Dfv=brbs:brbsfv.

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

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

Hence, Dfu+Dfv is an arithmetic progression.

Conversely, assume that Dfu+Dfv is an arithmetic progression. Then, by previous step, we have Dfu+Dfv=DA, where A=fu+fv. Then, we have DA is an arithmetic progression. Since the difference set DA is an arithmetic progression, then by the above remark, we have A=fu+fv=f+uv is also an arithmetic progression. Hence, the edge e=uv has 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 [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 G are the same.

Case 2: Assume that u,v be any two adjacent vertices in G with common differences du and dv respectively such that dudv. Also, assume that fu=ar=a+rdu:0r<m and fv=bs=b+sdv:0s<n. Then, fu=m and fv=n. Now, arrange the terms of fu+fv=f+uv in rows and columns as follows. For any bsfv,0s<n, arrange the terms of A+bs in 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=kdu and km. If k<m, then for any afu and bfv we 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 du itself. If k=m, then the difference between the final element of each row and the first element of the next row is du and the difference between two consecutive elements in each row is du. Hence, if km, then f+uv is 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 dj is not a multiple of di (or di is 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+vivj are 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=kdi where 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 vi and vj of G with common differences di and dj respectively, either di=dj, or if dj>di,dj=kdj, where k is 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 vi and vj of G, dj=kdj,kfvi, where di is the smallest among the common differences of the vertices of G. If vr is another vertex that is adjacent to vj, then it has the common difference dr which is equal to either di or dj or ldj. In all the three cases, dr is a multiple of di. Hence, the greatest common divisor of di,dj,dr is 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 uivj has the common difference di. The edge vjvk has the common difference di, if dk=di, or dj in 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 [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 let di and dj be the common differences of two adjacent vertices vi and vj in G. If fvifvj, then for some positive integer 1kfvi, the edge vivj has the set-labelling number fvi+kfvj1.

Proof. Let f be an arithmetic modular sumset labelling defined on G. For any two vertices vi and vj of G, let fvi=aiai+diai+2diai+3diai+m1di and let fvj=ajaj+djaj+2djaj+3djaj+n1dj. Here fvi=m and fvj=n.

Let di and dj be the common differences of the vertices vi and vj respectively, such that di<dj. Since f is an arithmetic modular sumset labelling on G, by Theorem 3.2, there exists a positive integer k such 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 vivj is m+kn1. □

Advertisement

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:VGP0Zn defined 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:VGP0Zn of a given graph G is a strongly modular sumset labelling of G if and only if DfuDfv=Ø,uvEG, where fufvn.

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

Let uv be 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,ajfu and br,bsfv, we have ai+braj+bs in f+uvuvEG. That is, aiajbsbr for any ai,ajfu and 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 uv in G. That is, aiajbsbr for any ai,ajfu and br,bsfv. Then, aiajbsbr. That is, ai+braj+bs. Therefore, all elements in fu+fv are distinct. That is, f+uv=fufv for 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 fufv cannot 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. [47] For a positive integer kn, a modular sumset labelling f:VGP0Zn of a given connected graph G is a strongly k-uniform modular sumset labelling of G if and only if either k is a perfect square or G is bipartite.

Proof. If k is 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 k is not a perfect square.

Let G be a bipartite graph with bipartition XY. Let r,s be two divisors of k. Label all vertices of X by distinct r-element sets all of whose difference sets are the same, say DX. Similarly, label all vertices of Y by 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 v be a vertex of G with the set-labelling number r, where r is 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 r or s. Let X be the set of all vertices of G having the set-labelling number r and Y be 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. [47] For a positive non-square integer kn, a modular sumset labelling f:VGP0Zn of 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. [47] 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 r and s of k such 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 G be a graph which admits an arithmetic modular sumset labelling, say f. Then, f is a strongly modular sumset labelling of G if and only if the deterministic ratio of every edge of G is equal to the set-labelling number of its end vertex having smaller common difference.

Proof. Let f be an arithmetic modular sumset labelling of G. Let vi and vj are two adjacent vertices in G and di and dj be their common differences under f. Without loss of generality, let di<dj. Then, by Theorem 3.4, the set-labelling number of the edge vivj is fvi+kfvj1.

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

fvi+kfvj1=fvifvjkfvj1=fvifvj1k=fvi.

Conversely, assume that the common differences di and dj of two adjacent vertices vi and vj respectively in G, where di<dj such that dj=fvi.di. Assume that fvi=ar=a+rdi:0r<fvi and fvj=bs=b+skdi:0s<fvj, where kfvi. Now, arrange the terms of f+vivj=fvi+fvj in rows and columns as follows. For bsfvj,0s<fvj, arrange the terms of fvi+bs in 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+fvj is fvifvj. Hence, f is a strongly modular sumset labelling.□

Advertisement

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:VGP0Zn of 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:VGPZn of a given graph G is a supreme modular sumset labelling of G if the set-label of every edge of G is the ground set Zn itself.

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

Theorem 5.1. [47] The modular sumset labelling f:VGPZn of a given graph G is a supreme modular sumset labelling of G if and only if for every pair of adjacent vertices u and v of G some or all of the following conditions hold.

  1. fu+fvn if DfuDfvØ. The strict inequality hold when Dfu and Dfv are arithmetic progressions containing the same elements.

  2. fufvn if DfuDfv=Ø.

Proof. For two adjacent vertices u and v in G, let Dfu=Dfv=d are arithmetic progressions containing the same elements. Then, the elements in fu and fv are 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 uv is n if and only if fu+fv>n.

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

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

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

Theorem 5.2. [47] Let f be a strong sumset-labelling of a given graph G. Then, f is a maximal sumset-labelling of G if and only if n is a perfect square or G is bipartite or a disjoint union of bipartite components.

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

Advertisement

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 A and B be two non-empty subsets of Zn such 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=1 or 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 f of a graph G is said to be a weakly modular sumset labelling of G if the cardinality of the set-label of every edge of G is 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 uv in weakly modular sumset graph G, f+uv=fu or 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 G with set-labelling number 1 is 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 [39]), we have.

Theorem 6.1. A graph G admits a weak modular sumset labelling if and only if G is bipartite or contains sparing edges.

Proof. Note the fact that at least one end vertex of every edge of G is 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 G has exactly one end vertex with singleton set-label, then we can partition the vertex set of G into two subsets X with all sparing vertices and Y with all non-sparing vertices. Here, no two vertices in the same partition are adjacent and hence G is a bipartite graph. If G is not a bipartite graph, then obviously G should have at least one sparing edge, completing the proof.

Invoking Theorem 6.1, the following two results are immediate.

Corollary 6.2. Every graph G admits a weakly modular sumset labelling.

Corollary 6.3. A graph G admits a weakly uniform modular sumset labelling if and only if G is bipartite.

The above results are similar to the corresponding result of integer additive set-labelled graphs (see [39]) and hence the notion of sparing number of 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 G be a weakly modular sumset labelled graph. Then, the sparing number of G is the number of sparing edges in G.

A set of vertices X of a graph G is 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. Let G be a weakly modular sumset labelled graph and I be I be the largest independent set of G with maximum incidence. Then, the sparing number of G is 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 viI can have a non-singleton set-label which gives non-singleton set labels to dvi edges incident on it. Since I is an independent set, the edges incident at the vertices in I assumes non-singleton set-label. Therefore, the number of edges having non-singleton set-label incident at the vertices in I is viIdvi. Since I is 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 G is 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 number of a graph G, denoted by σw is defined to be the minimum value of n such that a modular sumset labelling f:VGP0Zn is a weakly modular sumset labelling of G.

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

Theorem 6.5. [47] Let G be a modular sumset graph and α and β be the covering number and independence number of G respectively. Then, the weak modular sumset number of G is maxαr, where r is the smallest positive integer such that 2rr1β.

Proof. Recall that αG+βG=VG (see [4]). Since G is 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 V be the set of these independent vertices in G. Therefore, the minimum number of sparing vertices is VGβ=α. Since all these vertices in VV must 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 V cannot be labelled by non-singleton subsets of this ground set. We know that the number of non-empty, non-singleton subsets of a set A is 2AA1, where AZn is the ground set used for labelling.

Therefore, the weak modular sumset number G is α if 2αα1β. Otherwise, the ground set must have at least r elements such that 2rr1β. Therefore, in this case, the weak modular sumset number of G is r, where r is 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; p2 if p>2
Cycle, Cpp1 if p=3,4; p2 if p>4
Wheel graph, W1,p1 + p2
Helm graph, Hpp
Ladder graph, Lpp
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 G admits a weakly uniform modular sumset labelling.

Theorem 6.6. [47] Let G be a weakly k-uniform modular sumset graph with covering number α and independence number β, where k<α. Then, the minimum cardinality of the ground set Zn is 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 G over the ground set AZn. Then, by Corollary 6.3, G is bipartite. Let X,Y be the bipartition of the vertex set VG. Without loss of generality, let XY. Then, α=X and β=Y. Then, distinct elements of X must have distinct singleton set-label. Therefore, nα.

On the other hand, since f is k-uniform, all the elements in Y must have distinct k-element set-label. The number of k-element subsets of a set A (obviously, with more than k elements) is Ak. The ground set A has α elements only if αkβ. Otherwise, the ground set A must contain at least r elements, 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 G be a weakly k-uniform modular sumset graph, where kα, where α is the covering number of G. Then, the minimum cardinality of the ground set Zn is the smallest positive integer n such 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 G to be a maximal modular sumset labelling of G.

Proposition 6.8. [47] A weakly modular sumset labelling of a graph G is a supreme modular sumset labelling of G if and only if G is a star graph.

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

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

Advertisement

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 Zn can 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.

Advertisement

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.

Advertisement

Additional information

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
  7. 7. Brandstadt A, Spinrad JP. Graph Classes: A Survey. Vol. 3. Philadelphia: SIAM; 1999
  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;1 jfsva-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

Sudev Naduvath

Submitted: 20 November 2019 Reviewed: 29 April 2020 Published: 08 August 2020