Sumset Valuations of Graphs and Their Applications

Sumset Valuations of Graphs and Their Applications

Sudev Naduvath (Christ University, India), Germina K. Augusthy (Central University of Kerala, India) and Johan Kok (Tshwane Metropolitan Police Department, South Africa)
DOI: 10.4018/978-1-5225-9380-5.ch009

Abstract

Graph labelling is an assignment of labels to the vertices and/or edges of a graph with respect to certain restrictions and in accordance with certain predefined rules. The sumset of two non-empty sets A and B, denoted by A+B, is defined by A+B=\{a=b: a\inA, b\inB\}. Let X be a non-empty subset of the set \Z and \sP(X) be its power set. An \textit{sumset labelling} of a given graph G is an injective set-valued function f: V(G)\to\sP_0(X), which induces a function f+: E(G)\to\sP_0(X) defined by f+(uv)=f(u)+f(v), where f(u)+f(v) is the sumset of the set-labels of the vertices u and v. This chapter discusses different types of sumset labeling of graphs and their structural characterizations. The properties and characterizations of certain hypergraphs and signed graphs, which are induced by the sumset-labeling of given graphs, are also done in this chapter.
Chapter Preview
Top

Introduction

In graph theory, graph labelling is an assignment of labels to the vertices and/or edges of a graph with respect to certain restrictions and in accordance with certain predefined rules. For the past few decades, graph labelling has become a fruitful research area in graph theory. Different graph labellings have resulted from practical considerations. They are not only of theoretical interests but have many practical implications also. For many applications, the edges or vertices of a given graph are given labels that are meaningful in the context.

Graph Labelling

Valuation of a graph 978-1-5225-9380-5.ch009.m01 is a one to one mapping of the vertex set of 978-1-5225-9380-5.ch009.m02 on to the set of all integers 978-1-5225-9380-5.ch009.m03. Graph labeling has become a fertile research area in graph theory after the introduction of the notion of certain types number valuations, called 978-1-5225-9380-5.ch009.m04-valuations, of graphs in Rosa (1967). The most popular one among the number valuations of graphs is 978-1-5225-9380-5.ch009.m05-valuation or graceful labelling of a graph (see Golomb, 1972; Rosa, 1967) which is defined as an injective function

978-1-5225-9380-5.ch009.m06
such that, when each edge 978-1-5225-9380-5.ch009.m07 is assigned the label 978-1-5225-9380-5.ch009.m08, the resulting edge labels are distinct. A graph 978-1-5225-9380-5.ch009.m09 is said to be edge-graceful if there exists a bijection
978-1-5225-9380-5.ch009.m10
such that the induced mapping
978-1-5225-9380-5.ch009.m11
given by
978-1-5225-9380-5.ch009.m12
taken over all edges 978-1-5225-9380-5.ch009.m13 is a bijection.

Motivated by various problems in social networks, a set analogue of number valuations called set-valuation of graphs, has been introduced in Acharya (1983). In the number valuations, the elements of a graph are assigned to numbers while in the set-valuations, the elements of a graph are assigned to sets subject to certain conditions. The mathematical definition of a set-valuation of a graph concerned is as given below (see Acharya, 1983):

For a graph 978-1-5225-9380-5.ch009.m14 and a non-empty set 978-1-5225-9380-5.ch009.m15, a set-labeling or a set-valuation of 978-1-5225-9380-5.ch009.m16, with respect to the set 978-1-5225-9380-5.ch009.m17, is an injective set-valued function

978-1-5225-9380-5.ch009.m18
such that the function
978-1-5225-9380-5.ch009.m19
is defined by
978-1-5225-9380-5.ch009.m20
for every 978-1-5225-9380-5.ch009.m21, where 978-1-5225-9380-5.ch009.m22 is the set of all subsets of 978-1-5225-9380-5.ch009.m23 and 978-1-5225-9380-5.ch009.m24 is the symmetric difference of sets. The definition can be generalised by allowing any binary operation 978-1-5225-9380-5.ch009.m25 of two sets in place of the symmetric difference 978-1-5225-9380-5.ch009.m26 in the above definitions.

Many significant and interesting studies on set-labelling of graphs have been done in the last two decades (see [1-10, 32, 33, 91]).

Key Terms in this Chapter

Sequential Sumset Labeling: A sumset labeling with the collection of all vertex set-set-labels and edge-set-labels together with the nullset form the powerset of the ground set.

Weak Sumset Labeling: A sumset labeling in which the set-indexing number of each edge is equal to that of at least one of its end vertices.

Set-Indexing Number of an Element: The cardinality of the set-label of that element.

Set-Label Hypergraphs: The hypergraphs whose elements are the set-labels of the elements of a sumset graph.

Strong Sumset Labeling: A sumset labeling in which the set-indexing number of every edge is the product of the set-indexing numbers of its end vertices.

Sumset Signed Graph: A signed graph with a sumset labeling and whose signs are induced by the set-labels of its elements.

Graceful Sumset Labeling: A sumset labeling with the collection of all edge set-set-labels together with the null set and {0} form the power set of the ground set.

Sumset Labeling: An assignment of number sets to the elements of a graph such that the set-label of each edge is the sumset of the set-labels of its end vertices.

Arithmetic Sumset Labeling: A sumset labeling in which the set-labels of all vertices and edges of the graph are arithmetic progressions.

Topogenic Sumset Labeling: A sumset labeling with the collection of all vertex set-set-labels and edge-set-labels together with the nullset form a topology of the ground set.

Complete Chapter List

Search this Book:
Reset