International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 372
ISSN 2229-5518
A Creative Review on Integer Additive Set-Valued
Graphs
N. K. Sudev, K. A. Germina, K. P. Chithra
AbstractβFor a non-empty ground set π, finite or infinite, the set-valuation or set-labeling of a given graph πΊ is an injective function π: π(πΊ ) β
π«(π), with induced edge-function π β: πΈ(πΊ) β π« (π) is defined by π +(π’π’) = π(π’) β π(π’); π’π’ β πΈ(πΊ), where π«(π) is the power set of π and β is a pre-
defined binary operation on sets. A set-labeling π of a graph πΊ is called a set-indexer if the induced function πβ is also injective. An integer additive
set-labeling is defined as an injective function π: π(πΊ ) β π«(β0 ) such that the induced function π + : πΈ(πΊ) β π«(β0) defined by π +(π’π’) = π (π’) + π(π’)
is also injective, where β0 is the set of all non-negative integers, π«(β0 ) its power set π(π’) + π(π’) isthe sumset of the set-labels π(π’) and π(π’) of
the vertices π’ and π’ in πΊ. In this paper, we critically and creatively review the concepts and properties of integer additive set-valued graphs.
.
ββββββββββ ο΅ ββββββββββ
OR all terms and definitions, not defined specifically in this paper, we refer to [23]. Unless mentioned otherwise, all graphs considered here are simple, finite and have no
isolated vertices.
The researches on graph labeling problems commenced with the introduction of the concept of number valuations of graphs in [29]. Since then, the studies on graph labeling have contributed significantly to the researches in graph theory and associated fields. Graph labeling problems have numerous theoretical and practical applications. Many types of graph labelings are surveyed and listed in [16].
Motivated from certain problems related to social interactions and social networks, Acharya introduced, in [1], the notion of set-valuation of graphs analogous to the number valuations of
graphs. For a non-empty ground set π, finite or infinite,the set- valuation or set-labeling of a given graph πΊ is an injective function π: π(πΊ) β π«(π), where π«(π) is the power set of the set π.
Also, in [1], a set-indexer of a graph πΊ is defined as an injective set-valued function π: π(πΊ) β π«(π) such that the function
πβ : πΈ(πΊ) β π«(π) β {β
} defined by πβ (π’π’) = π(π’) β π(π’) for every π’π’ β πΈ(πΊ) is also injective, where π«(π) is the set of all subsets of π and β is a binary operation on sets.
ββββββββββββββββ
β’ Department of Mathematics, Vidya Academy of Science & Technology, Thalakkottukara, Thrissur-680501, India. E-mail: sudevnk@gmail.com
β’ PG & Research Department of Mathematics, Marymatha Arts & Science
College, Mananthavady-670645, India., E-mail: srgerminaka@gmail.com
β’ Naduvath Mana, Nandikkara, Thrissur-680301, India. E-email: chithrasudev@gmail.com
Taking the symmetric difference of two sets as the operation
between two set-labels of the vertices of πΊ, the following theo-
rem was proved in [1].
Theorem 1.1. [1] Every graph has a set-indexer.
Let π΄ and π΅ be two non-empty sets. The sumset of π΄ and π΅ is denoted by π΄ + π΅ and is defined as π΄ + π΅ = {π + π: π β π΄, π β
π΅}. If a set πΆ is the sumset of two sets π΄ and π΅, then π΄ and π΅ are said to be the summands of πΆ. Note that for any set π΄, we can write π΄ = π΄ + {0}. Here, π΄ and {0} are said to be the non- trivial summands of the set π΄. The sumsets and summands are
non-trivial unless mentioned otherwise.
For any positive integer π, an π-integral multiple of a set π΄, de- noted by π. π΄ and is defined as π. π΄ = {ππ: π β π΄}. We denote the cardinality of a set π΄ by |π΄|. Hence, 2π΄ = π΄ + π΄ and
2. π΄ = {2π: π β π΄} and |2π΄| > |π΄| where as |2. π΄| = |π΄|.
In this work, we review the studies on the graphs which admit
a particular type of set-labeling called integer additive set-
labeling, defined in terms of the sumsets of given sets of non-
negative integers.
The notion of integer additive set-labeling of a graph was in- troduced as follows, using the concept of sumsets of two sets of non-negative integers, as follows.
Definition 2.1. Let β0 be the set of all non-negative integers and let π«(β0) be its power set. A function π: π(πΊ) β π«(β0), whose associated function π+ (π’π’): πΈ(πΊ) β π«(β0 ) is defined by
π+ (π’π’) = π(π’) + π(π’), is said to be an integer additive set- labeling if it is injective. A graph πΊ which admits an integer
additive set-labeling is called an integer additive set-labeled graph
or integer additive set-valued graph.
IJSER Β© 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 373
ISSN 2229-5518
The notion of integer additive set-indexers of graphs was first appeared in [17] as follows.
Definition 2.2. An integer additive set-indexer (IASI) of a graph
πΊ is defined as an injective function π: π(πΊ) β π«(β0) such that the induced function π+ : πΈ(πΊ) β π«(β0) defined by π + (π’π’) =
π(π’) + π(π’) = {π + π: π β π(π’), π β π(π’)} is also injective. A
graph πΊ which admits an IASI is called an integer additive set-
indexed graph.
In this discussion, we denote the associated function of an
IASL π, defined over the edge set of πΊ by π +.
Definition 2.3. An IASL (or IASI) is said to be π-uniform if
|π+ (π)| = π for all π β πΈ(πΊ). That is, a connected graph πΊ is
said to have a π-uniform IASL if all of its edges have the same
set-indexing number π.
If either π(π’) or π(π’) is countably infinite, then their sumset
will also be countably infinite and hence the study of the car-
dinality of the sumset π(π’) + π(π’) becomes countably infinite.
Hence, we restrict our discussion to finite sets of non-negative
integers.
Certain studies about integer additive set-indexed graphs have been done in [5], [18], [32] and [31]. The following are the important terms and definitions made in these papers.
The cardinality of the set-label of an element (vertex or edge)
of a graph πΊ is called the set-indexing number of that element. If the set-labels of all vertices of πΊ have the same cardinality, then the vertex set π(πΊ) is said to be uniformly set-indexed. A graph is said to admit (π, π)-completely uniform IASI (or IASL) π
if π is a π-uniform IASL (or IASI) and π(πΊ) is π-uniformly set-
indexed.
Analogous to Theorem 1, we have proved the following theo- rem.
Theorem 2.4. Every graph has an integer additive set-labeling.
The proof follows from the fact that the sumset of two sets of non-negative integers is again a set of non-negative integers.
The following theorem was proved in [31] by choosing the set-
labels of the vertices of a given graph πΊ in a suitable manner.
The sumsets of different pairs of sets non-negative integers need not be distinct in all cases. But we can establish the exist-
ence of an IASI for any given graph πΊ if we choose the set- labels of the vertices of πΊ suitably in such a way that no two edges of πΊ have the same set-indexing number.
We know that if π΄ and π΅ are two sets of non-negative integers, then their sumset π΄ + π΅ is also a set of non-negative integers. That is, if π΄, π΅ β β0 , then π΄ + π΅ β β0. This property leads us to
the following results on certain operations andproducts of
IASL graphs.
First, we consider the union of two IASL graphs.
(induced) IASL (or IASI).
Proof. Let πΊ1 and πΊ2 be two graphs that admit the IASLs π1 and π2 respectively, chosen in such a way that π1 and π2 are the same for the common vertices of πΊ1 and πΊ2, if any. Then, de- fine a function π on πΊ1 βͺ πΊ2, such that π = π1 for all vertices in
πΊ1 and π = π2 for all vertices in πΊ2 such that the associated function π+ of π is defined as π+ (π’π’) = π1 (π’) + π1 (π’) if
π’π’ β πΈ(πΊ1 ) and π+ (π’π’) = π2(π’) + π2 (π’) if π’π’ β πΈ(πΊ2 ). Clearly,
π is an IASL of πΊ1 βͺ πΊ2. ο
Next, in the following theorem, we check whether the join of
two IASL graphs is an IASL graph.
(induced) IASL (or IASI).
Proof. Let πΊ1 and πΊ2 be two graphs that admit the IASLs π1 and π2 respectively. Consider the join πΊ = πΊ1 + πΊ2. Define a function π on πΊ in such a way that π = π1 for all vertices in πΊ1 and π = π2 for all vertices in πΊ2 and the associated function
π+ : πΈ(πΊ) β π«(β0 ) of π is defined as as π+ (π’π’) = π1 (π’) + π1 (π’)
if π’π’ β πΈ(πΊ1 ) and π+ (π’π’) = π2 (π’) + π2 (π’) if π’π’ β πΈ(πΊ2 ). Clear-
ly, π is an IASL of πΊ1 βͺ πΊ2. .
ο
The following theorem is on the admissibility of an IASL by the complement of an IASL-graph.
graph.
Proof. The proof follows from the fact that a graph πΊ and its complement πΊ have the same set of vertices and hence have the same set of set-labels. That is, an IASL π defined on a graph πΊ is an IASL of the complement of πΊ also.
ο
Now, recall the definitions of the certain fundamental prod- ucts of two graphs given in [22].
Let πΊ1 (π1 , πΈ1 ) and πΊ2 (π2, πΈ2 ) be two graphs. Then, the Cartesian product of πΊ1 and πΊ2, denoted by πΊ1 β‘ πΊ2, is the graph with ver- tex set π1 Γ π2 defined as follows. Let π’ = (π’1, π’2 ) and π’ = (π’1, π’2) be two points in π1 Γ π2. Then, π’ and π’ are adjacent in
πΊ1 β‘πΊ2 whenever [π’1 = π’1 and π’2 is adjacent to π’2] or [π’2 = π’2
and π’1 is adjacent to π’1].
The direct product of two graphs πΊ1 and πΊ2, is the graph whose
IJSER Β© 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 374
ISSN 2229-5518
vertex set is π(πΊ1 ) Γ π(πΊ2) and for which the vertices (π’, π’) and (π’β², π’ β² ) are adjacent if π’π’β² β πΈ(πΊ1 ) and π’π’ β² β πΈ(πΊ2 ). The direct product of πΊ1 and πΊ2 is denoted by πΊ1 Γ πΊ2.
The strong product of two graphs πΊ1 and πΊ2 is the graph, de- noted by πΊ1 β πΊ2, whose vertex set is π(πΊ1 ) Γ π(πΊ2) and for which the vertices (π’, π’) and (π’β² , π’ β² ) are adjacent if [π’π’β² β
πΈ(πΊ1 ) and π’ = π’ β² ] or [π’ = π’β² and π’π’ β² β πΈ(πΊ2 )] or [π’π’β² β πΈ(πΊ1)
and π’π’ β² β πΈ(πΊ2)].
The lexicographic product or composition (see [24]) of two graphs
πΊ1 and πΊ2 is the graph, denoted by πΊ1 β πΊ2, is the graph whose vertex set π(πΊ1) Γ π(πΊ2) and for two vertices (π’, π’) and (π’β², π’ β² ) are adjacent if [π’π’β² β πΈ(πΊ1)] or [π’ = π’β² and π’π’ β² β πΈ(πΊ2 )].
Now we proceed to verify whether these products of two
IASL graphs admit IASLs.
Proof. Let π’1 , π’2 , β¦ , π’π be the vertices of πΊ1 and π’1 , π’2, β¦ , π’π be the vertices of πΊ2. Also let π1, π2 be the IASLs defined on πΊ1 and πΊ2 respectively. Now, define a function π on πΊ1 β‘πΊ2 such that π(π’π , π’π ) = π1 (π’1) + π2 (π’π ) where the associated function
π+ : (πΈ(πΊ1 β‘πΊ2)) β π«(β0) is defined by π + ((π’π , π’π ), (π’π , π’π )) =
π(π’π , π’π ) + π(π’π , π’π ). Therefore, π is an IASL on πΊ1 β‘πΊ2. ο
Using the definition of π for the vertices and the associated
function π+ for the edges, we can establish the existence of
IASLs for the other fundamental graph products also as stated
in the following results.
Next, we consider certain products of graphs in which we take finite number copies of any one of the two graphs and attach these copies to the vertices of the other graph using certain rules.
The most popular one among such graph products, is the co- rona of two graphs which is defined in [15] as follows.
The corona of two graphs πΊ1 and πΊ2, denoted by πΊ1 β πΊ2, is the graph obtained by taking |π(πΊ1)| copies of πΊ2 and then joining the π-th point of πΊ1 to every point of the π-th copy of πΊ2.
Another commonly used graph product in various literature, is the rooted product of two graphs, which is defined in [19] as follows.
The rooted product of a graph πΊ1 on π1 vertices and rooted graph πΊ2 on π2 vertices, denoted by πΊ1 β πΊ2, is defined as the graph obtained by taking π1 copies of πΊ2, and for every vertex
π’π of πΊ1 and identifying π’π with the root node of the π-th copy of πΊ2.
The admissibility of an IASL by these products of two IASL
graphs is established in the following theorem.
Theorem 3.8. The corona of two IASL graphs also admits an IASL. Proof. Let π’1 , π’2 , β¦ , π’π be the vertices of πΊ1 and let π’1, π’2, β¦ , π’π be the vertices of πΊ2. For 1 β€ π β€ π and 1 β€ π β€ π, let π’ππ be the
π-th vertex of the π-th copy of πΊ2. Now, label the vertex π’ππ of π-
th copyπΊ2 corresponding to vertex π’π of πΊ2 by the set ππ (π’ππ ) =
π. π(π’π ). Let the set-label of an edge in πΊ be the sumset of the
set-labels of its end vertices. Clearly, this labeling is an IASL
on πΊ1 β πΊ2. ο
IASL graph.
Proof. In the rooted product πΊ1 β πΊ2, for 1 β€ π β€ |π(πΊ1 )|, the roots of the π-th copy of πΊ2 is identified with the π-th vertex of
πΊ1. Label these identified vertices by the corresponding set- labels of πΊ1. All other vertices in the different copies of πΊ2 by
distinct integral multiples of the set-labels of corresponding
vertices of πΊ2. Also, let the set-labels of edges in πΊ1 β πΊ2 be the
sumset of the set-labels of their end vertices. Clearly, this set-
labeling is an IASL on πΊ1 β πΊ2.
ο
An IASL of a graph πΊ induces an IASL to certain other graphs associated to πΊ. The induction property of a IASL of a graph πΊ
to various associated graphs of πΊ is studied in [31]. The major
concepts and findings in this paper are mentioned in this sec-
tion. More over, we establish some new results in this area.
An obvious result about an IASI π of a given graph πΊ is its hereditary nature. The following theorem shows that an IASI
of a given graph induces an IASI on any subgraph of πΊ.
Proposition 4.1. [31] If a given graph πΊ admits an IASL (or IASI)
π, then any subgraph π» of πΊ also admits an IASI πβ , the restriction
of π to π(π»). That is, the existence of an IASL for a graph πΊ is a
hereditary property.
If we replace an element (a vertex or an edge) of πΊ by another element (a vertex or an edge) which is not in πΊ to form an as- sociated graph structure, say πΊ β², it is customary that the com- mon elements of the graph πΊ and the associated graph πΊ β² pre-
serve the same set-labels and the newly introduced elements
assume the same set-label of the corresponding deleted ele-
ments of πΊ. That is, the IASI defined on πΊ induces an IASI for the graph πΊ β². The IASI, thus defined for the newly formed graph πΊ β²is called an induced IASI of πΊ β².
IJSER Β© 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 375
ISSN 2229-5518
This induction property of integer additive set-labeling holds
not only for the subgraphs of an IASI graph πΊ, but also for certain other graph structures associated with πΊ such as mi-
nors, topological reductions etc.
In the following results, we consider only the IASL of the as- sociated graph which are induced from the IASL of the graph
πΊ concerned.
By an edge contraction in πΊ, we mean an edge, say π, is re-
moved and its two incident vertices, π’ and π’, are merged into
a new vertex π€, where the edges incident to π€ each corre-
spond to an edge incident to either π’ or π’.
The existence of an IASI for the graph obtained by contracting
finite edges of an IASL graph πΊ is established in the following
theorem.
Proposition 4.2. [31] Let πΊ be an IASI graph and let π be an edge
of πΊ. Then, πΊ β π admits an IASI.
An undirected graph π» is called a minor of a given graph πΊ if
π» can be formed from πΊ by deleting edges and vertices and by
contracting edges.
Proposition 4.3. Let πΊ be an IASI graph and let π» be a minor of πΊ. Then, π» admits an IASI.
The proof of this result is an immediate consequence of Propo- sition 4.1 and 4.2.
Let πΊ be a connected graph and let π’ be a vertex of πΊ with
π(π’) = 2. Then, π’ is adjacent to two vertices π’ and π€ in πΊ. If π’
and π’ are non-adjacent vertices in πΊ, then delete π’ from πΊ and
add the edge π’π€ to πΊ β {π’}. This operation is called an elemen-
tary topological reduction on πΊ. Then, we have
Proposition 4.4. [31] Let πΊ be a graph which admits an IASI. Then
any graph πΊ β², obtained by applying finite number of elementary
topological reductions on πΊ, admits an IASI.
A subdivision or an expansion of a graph is the reverse opera-
tion of an elementary topological reduction. Under this opera-
tion, we introduce a new vertex, say π€, to an edge π’π’ in πΊ. Thus, the vertex π€ replaces the edge π’π’ and two edges π’π€ and
π€π’ are introduced to πΊ β π’π’ βͺ {π€}. Two graphs πΊ and πΊ β² are
said to be homeomorphic if there is a graph isomorphism from
some subdivision of πΊ to some subdivision of πΊ β².
The following theorem establishes the existence of an induced
IASL for a graph πΊ β² which is homeomorphic to a given IASL
graph πΊ.
subdivision πΊ β² of πΊ admits an (induced) IASL (or IASI).
Proof. Let π be an IASL defined on a given graph πΊ and let π’, π’
be two adjacent vertices in πΊ. Introduce a new vertex π€ on the edge π’π’ so that π’π’ is subdivided to two edges π’π€ and π€π’. Let
πΊ β² = [πΊ β (π’π’)] βͺ {π’π€, π’π€}. Define a function π: π(πΊ β²) β
π«(β0) such that π(π’) = π(π’) if π’ β π(πΊ) and π(π€) = π+ (π’π’).
Clearly, π is an IASL on πΊ β². This result can be extended to a
graph obtained by finite number of subdivisions on πΊ. There
fore, any subdivision of an IASL graph admits an (induced)
IASL. ο
Invoking Proposition 5, the admissibility of an IASL by a graph that is homeomorphic to a given IASL graph.
Proposition 4.6. Let πΊ be an IASL (or IASI) graph and let π» be a a graph that is homeomorphic to πΊ. Then, π» admits an IASL (or
IASI).
Proof. Assume that the graphs πΊ and π» are homeomorphic graphs. Let πΊ β² and π»β² be the isomorphic subdivisions of πΊ and
π» respectively. Let π be an IASL defined on πΊ. By Proposition
5, the subdivision πΊ β² admits an IASL, say πβ² induced by π.
Since πΊ β² β
π»β², define a function π: π(π»β² ) β π«(β0 ) by π(π’ β²) =
π(π’), where π’ β² is the vertex in π»β² corresponding to the vertex π’
of πΊ β². That is, π assigns the same set-labels of the vertices of πΊ β²
to the corresponding vertices of π»β². Therefore, π(π(π»β² )) =
π(π(πΊ β²)). Since π» can be considered as a graph obtained by
applying a finite number of topological reductions on π»β², by
Proposition 4, π induces an IASL on π». Therefore, π» is an IASL
graph. ο
The existence of integer additive set-labelings for certain other
graphs associated to the given graph πΊ, which are not ob- tained by replacing some elements of πΊ by certain other ele- ments not in πΊ, have been established in [31].
An important graph of this kind which is associated to a given
graph πΊ is the line graph of πΊ which is defined as follows.
For a given graph πΊ, its line graph πΏ(πΊ) is a graph such that
each vertex of πΏ(πΊ) represents an edge of πΊ and two vertices of
πΏ(πΊ) are adjacent if and only if their corresponding edges in πΊ
incident on a common vertex in πΊ. The following theorem es-
tablishes the existence of IASI by the line graph of a graph. Theorem 4.7. [31] If a graph πΊ admits IASI, say π, then its line graph πΏ(πΊ) also admits an (induced) IASI.
Another graph that is associated to a given graph is its total graph which is defined as follows.
The total graph of a graph πΊ is the graph, denoted by π(πΊ), is the graph having the property that a one-to one correspond-
ence can be defined between its points and the elements (ver-
tices and edges) of πΊ such that two points of π(πΊ) are adjacent
if and only if the corresponding elements of πΊ are adjacent
(either if both elements are edges or if both elements are verti-
ces) or they are incident (if one element is an edge and the
other is a vertex).
The following theorem establishes the existence of an IASI for
IJSER Β© 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 376
ISSN 2229-5518
the total graph of a graph.
Theorem 8. [31] If a graph πΊ admits IASI, say π, then its total graph π(πΊ) also admits an (induced) IASI.
So far, we discussed about the integer additive set-labeling of
graphs with respect to the countably infinite set β0. Can we choose a finite set π as the ground set for labeling the vertices of a graph πΊ? This is possible only when the ground set π has
sufficiently large cardinality. Hence, the study about the car-
dinality of the ground set π arises much interest.
The minimum cardinality of the ground set that is required for
set-labeling a graph πΊ is called the set-indexing number of πΊ.
The following theorem determines the set-indexing number of
a given graph πΊ.
Theorem 4.9. [31] Let π be a finite set of non-negative integers and
let π: π(πΊ) β 2π β {β
} be an IASI on πΊ, which has π vertices. Then,
π has at least βπππ2 (π + 1)β elements.
The following theorem is special case of the above theorem
when the vertices of πΊ have the same set-indexing number.
Theorem 4.10. [31] Let π be a finite set of non-negative integers
and let π: π(πΊ) β 2π β {β
} be an IASI on πΊ, which has π vertices,
such that π(πΊ) is π-uniformly set-indexed. Then, π = πΆ(|π|, π).
We have discussed the cardinality of the ground set π for la-
beling the vertices of a given graph so that it admits an IASL.
The cardinality of the set-labels of the elements of πΊ is also
worth studying. Some studies in this area are reviewed in the
following section.
Certain studies on set-indexing numbers of the elements of the IASI-graphs have been done in [18], [32] and [31]. The set- theoretic foundations of the IASLs , established in these stud- ies, are reviewed in this section.
Let π΄ and π΅ be two non-empty sets of non-negative integers. Then the ordered pairs (π, π) and (π, π) in π΄ Γ π΅ are said to be compatible if π + π = π + π. If (π, π) and (π, π) are compatible, then we write (π, π) βΌ (π, π). Clearly, βΌ is an equivalence rela-
tion.
A compatible class with respect to an integer π is the subset of
π΄ Γ π΅ defined by {(π, π) β π΄ Γ π΅: π + π = π} and is denoted by
π’π .
All the compatibility classes need not have the same number
of elements but can not exceed a certain number. It can be not-
ed that exactly one representative element of each compatibil-
ity class π’π of π(π’) Γ π(π’) contributes an element to the set- label of the corresponding edge π’π’ and all other ππ β 1 ele-
ments are neglected and we call these elements as neglected
elements of the class π’π . The number of neglected elements in
the set-label of an edge π’π’ with respect to the set π(π’) Γ π(π’)
is called the neglecting number of that edge.
The compatibility classes which contain the maximum possi- ble number of elements are called saturated classes. The com- patibility class that contains maximum elements is called a maximal compatibility class. Hence, we have
Proposition 5.1. [31] The cardinality of a saturated class in π΄ Γ π΅
is π, where π = πππ ( |π΄|, |π΅|).
The number of distinct compatibility classes in π΄ Γ π΅ is called
the compatibility index of the pair of sets (π΄, π΅) and is denoted
by β§(π΄,π΅) . Hence, we have the following lemma.
Lemma 5.2. Let π be an IASI of a graph πΊ and π’, π’ be two vertices
of πΊ. The set-indexing number of an edge π = π’π’ of πΊ is given by
|π+ (π)| = |π(π’)| + |π(π’)| = β§(π(π’),π(π£)) .
The following result establishes the bounds for the set-
indexing number of the edges of an IASI graph, in terms of the
set-indexing numbers of their end vertices.
Lemma 5.3. [18] For an IASI π of a graph πΊ,
πππ ( |π(π’)|, |π(π’)|) β€ |π+ (π’π’)| = |π(π’) + π(π’)| β€
|π(π’)||π(π’)|, where π’, π’ β π(πΊ).
Theorem 5.4. Let π be an IASI of a graph πΊ and let π’ and π’ be two
adjacent vertices of πΊ. Let |π(π’)| = π and |π(π’)| = π. Then,
|π+ (π’π’)| = ππ β π, where π is the number of neglected elements in
π(π’) Γ π(π’).
An interesting question that arises in this context is about a
necessary and sufficient condition for an IASL of a given
graph πΊ to be a uniform IASL of πΊ. The following result pro- vides a platform for finding the conditions for a given graph πΊ
to admit a uniform IASL.
Proposition 5.5. Two adjacent edges ππ and ππ of a graph πΊ have the same set-indexing number if and only if the set-indexing number of
the common vertex of these edges is the quotient when the difference of the neglecting numbers of the edges is divided by the differences of set-indexing numbers of the end vertices that are not common to these edges.
Proof. Let ππ = π’π’π and ππ = π’π’π be two adjacent edges in the given graph πΊ. Let π be an IASL defined on πΊ. Also, let
|π(π’)| = π, |π(π’π )| = ππ and |π(π’π )| = ππ . Then, the set- indexing number of ππ is πππ β ππ and that of ππ is πππ β ππ where ππ and ππ are neglecting numbers of ππ and ππ respective-
ly.
Assume that ππ and ππ have the same set-indexing number. Then, πππ β ππ = πππ β ππ. That is, π = (ππ β ππ )/(ππ β ππ ).
Conversely, assume that the set-indexing number of the com- mon vertex of these edges is the quotient when the difference of the neglecting numbers of the edges is divided by the dif-
IJSER Β© 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 377
ISSN 2229-5518
ferences of set-indexing numbers of the end vertices that are
not common to these edges. That is, π = (ππ β ππ )/(ππ β ππ ). Hence, πππ β ππ = πππ β ππ.
Therefore, the edges have the same set-indexing number. ο
Due to the above proposition, we establish a necessary and sufficient condition for an IASL of a given graph to be a uni-
form IASL of πΊ.
Theorem 5.6. Let πΊ be a graph that admits an IASL π. Then, π is a
uniform IASL of πΊ if and only if the set-indexing number of the
common vertex of any two adjacent edges is the ratio of the difference
between their neglecting numbers to the difference betweenthe set- indexing numbers of their distinct end vertices.
In the following theorem, we prove a necessary and sufficient
condition for an IASL of a graph πΊ, which assigns uniform set- labels to the vertices of πΊ, to be a uniform IASL of πΊ.
Theorem 5.7. Let the graph πΊ admits an IASL π under which all vertices of πΊ are uniformly set-labeled. Then, π is a uniform IASL if and only if all edges of πΊ have the same neglecting number.
Proof. Let π(πΊ) be π-uniformly set-labeled. Then, for any ver- tex π’ in πΊ, |π(π’)| = π and π + (ππ )π+ (π’π’) = π2 β ππ .
Let π be a uniform IASI of πΊ. Then, for any two adjacent edges
ππ = π’π’π and ππ = π’π’π of πΊ, we have |π+ (ππ )| = |π+ (ππ )|. That is,
π2 β ππ = π2 β ππ and hence ππ = ππ .
Conversely, assume that all the edges of πΊ have the same ne-
glecting number, say π. Therefore, for any edge π = π’π’ of πΊ,
|π+ (π)| = |π(π’)|β|π(π’)| β π. Since the graph π(πΊ) is π-uniformly
set-labeled, |π(π’)| = π for all π’ β π(πΊ). Therefore, |π+ (π)| =
π2 β π for all edges π β πΈ(πΊ). That is, π is a uniform IASL. ο
A necessary and sufficient condition for a graph to have a 2-
uniform IASI is proved in [5] as follows.
Theorem 5.8. [5] A graph πΊ admits a 2-uniform IASI if and only if
πΊ is bipartite.
In view of Lemma 3 the following definitions are introduced
in [18] and [32].
Definition 5.9. [18] A weak IASI is an IASI π whose associated function is defined as |π+ (π’π’)| = max ( |π(π’)|, |π(π’)|) for all
π’, π’ β π(πΊ). A graph which admits a weak IASI may be called
a weak IASI graph. A weak IASI is said to be weakly uniform
IASI if |π+ (π’π’)| = π, for all π’, π’ β π(πΊ) and for some positive integer π.
Definition 5.10. [32] An IASI π is called a strong IASI if
|π+ (π’π’)| = |π(π’)||π(π’)| for all π’, π’ β π(πΊ). A graph which ad-
mits a strong IASI may be called a strong IASI graph. A strong
IASI is said to be strongly uniform IASI if |π+ (π’π’)| = π, for all
π’, π’ β π(πΊ) and for some positive integer π.
Form the above definitions it follows that if π; π(πΊ) β π«(β0) is
a weak (or strong) IASI defined on a graph πΊ, then for each
adjacent pair of vertices π’ and π’ of πΊ, each compatibility class
of the pair of set-labels π(π’) and π(π’) is a trivial class.
Let πΊ be an IASI graph. Then, the following result for πΊ was
proved in [18].
Lemma 5.11. [18] Let π: π(πΊ) β π«(β0) be an IASI defined on a graph πΊ. Let π’ and π’ be any two adjacent vertices in πΊ. Then,
|π+ (π’π’)| = πππ ( |π(π’)|, |π(π’)|) if and only if either |π(π’)| = 1 or
|π(π’)| = 1.
This lemma leads us to the following result.
Theorem 5.12. [31] An IASI π of a graph πΊ is a weak IASI of πΊ if and only if at least one end vertex of any edge in πΊ has the set- indexing number 1.
The following theorem describes a necessary and sufficient condition for a graph to admit a weakly uniform IASI.
Theorem 5.13. [31] A connected graph πΊ admits a weakly uniform
IASI π if and only if πΊ is a bipartite graph.
The necessary and sufficient condition for the sumset of two
sets to have maximum cardinality is established in the follow-
ing result.
Lemma 5.14. [32] Let π΄, π΅ be two non-empty subsets of β0. Let π·π΄
and π·π΅ be the sets of all differences between two elements in the sets
π΄ and π΅ respectively. Then, |π΄ + π΅| = |π΄|. |π΅| if and only if π·π΄ and
π·π΅ are disjoint.
The sets π·π΄ of all differences between two elements of set π΄ is
called the difference set of π΄.
In view of the above lemma, a necessary and sufficient condi-
tion for an IASI to be a strong IASI is established in [32] as
follows.
Theorem 5.15. [32] An IASI π of a graph πΊ is a strong IASI of πΊ if and only if the difference sets of the set-labels of any two adjacent
vertices in πΊ are disjoint sets.
The following theorem describes a necessary and sufficient
condition for a graph to admit a strongly uniform IASI.
Theorem 5.16. [32] A connected graph πΊ admits a strongly π- uniform IASI π if and only if πΊ is a bipartite graph or π is a (π, π)- completely uniform IASI of πΊ, where π = π2 .
So far, we have reviewed the studies about integer additive set-labelings and integer additive set-indexers of certain graphs and their characteristics. In this paper, we also propose some new results in this area. Certain problems regarding the admissibility of integer additive set-indexers by various other
IJSER Β© 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 3, March-2015 378
ISSN 2229-5518
graph classes are still open.
More properties and characteristics of different types of IASLs and IASIs, both uniform and non-uniform, are yet to be inves- tigated. There are some more open problems regarding neces- sary and sufficient conditions for various graphs and graph classes to admit certain IASIs. All these facts show that there is a wide scope for further researches in this area.
The authors dedicate this work to the memory of Professor Belamannu Devadas Acharya who introduced the concept of integer additive set-indexers of graphs.
[1] B. D. Acharya, Set-Valuations and Their Applications, MRI Lecture notes in Applied Mathematics, The Mehta Research Institute of Mathematics and Mathematical Physics, Allahabad, 1983.
[2] B. D. Acharya, Set-Indexers of a Graph and Set-Graceful Graphs, Bulletin of
Allahabad Mathematical Society, (2001), 1-23.
[3] B. D. Acharya and K. A. Germina, Strongly Indexable Graphs: Some New Per- spectives, Advanced Modeling and Optimisation, (1)(2013), 3-22.
[4] S. Alexander, The Mathematical Coloring Book, Springer-Verlag, 2008.
[5] T. M. K. Anandavally, A Characterisation of 2-Uniform IASI Graphs, Interna- tional Journal of Contemporary Mathematical Sciences, (10)(2013), 459-462.
[6] T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New
York, 1989.
[7] M. Behzad, Total graphs, in Graph Theory and Applications, (Editors: Y. Alavi, D. R. Lick, A. T. White), pp. 21-23, Springer, 1972.
[8] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan
Press, London, 1976.
[9] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, 2008.
[10] A. BrandstΓ€dt, V. B. Le and J. P. Spinrad, Graph Classes:A Survey, SIAM, Philadelphia, 1999.
[11] D. M. Burton, Elementary Number Theory, Tata McGraw-Hill Inc., New Del- hi, 2007.
[12] G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw-Hill Inc.,
2005.
[13] G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
[14] N. Deo, Graph theory With Application to Engineering and Computer Science, Prentice Hall of India, 1974.
[15] R. Frucht and F. Harary On the Corona of Two Graphs, Aequationes Mathe- maticae, (3)(1970), 322-325.
[16] J. A. Gallian, A Dynamic Survey of Graph Labelling, The Electronic Journal of
Combinatorics (DS #16), 2013.
[17] K. A. Germina and T. M. K. Anandavally, Integer Additive Set-Indexers of a Graph: Sum Square Graphs, Journal of Combinatorics, Information and Sys- tem Sciences, (2-4)(2012), 345-358.
[18] K. A. Germina, N. K. Sudev, On Weakly Uniform Integer Additive Set- Indexers of Graphs, International Mathematical Forum, (37-40)(2013), 1827-
1834.
[19] C. D. Godsil and B. D. McKay, A New Graph Product and its Spectrum, Bulle- tin of Australian Mathematical Society, (1978), 21-28.
[20] J. T. Gross and J. Yellen, Graph Theory and its Applications, CRC Press, 2006. [21] G Hahn and G Sabidussi, Graph Symmetry: Algebraic Methods and Applica-
tions, NATO Advanced Science Institute Series-C 497, Springer, 1997.
[22] R. Hammack, W. Imrich and S. Klavzar Handbook of Product graphs, CRC Press, (2011).
[23] F. Harary, Graph Theory, Addison-Wesley, 1969.
[24] W. Imrich, S. Klavzar, Product Graphs: Structure and Recognition, Wiley, 2000. [25] K. D. Joshi, Applied Discrete Structures, New Age International, 2003.
[26] M. B. Nathanson, Additive Number Theory, Inverse Problems and Geometry of Sumsets, Springer, New York, 1996.
[27] M. B. Nathanson, Elementary Methods in Number Theory, Springer-Verlag, New York, 2000.
[28] M. B. Nathanson, Additive Number Theory: The Classical Bases, Springer- Verlag, New York, 1996.
[29] A. Rosa, On certain valuation of the vertices of a graph, in Theory of Graphs, Gordon and Breach, 1967.
[30] K. H. Rosen, Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.
[31] N. K. Sudev and K. A. Germina, On Integer Additive Set-Indexers of Graphs, International Journal of Mathematical Sciences & Engineering Applications, (II)(2014), 11-22.
[32] N. K. Sudev and K. A. Germina, Some New Results on Strong Integer Addi- tive Set-Indexers, Discrete Mathematics, Algorithms and Algorithms,
(1)(2015), 11-pages.
[33] E. W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC press, 2011.
[34] D. B. West, Introduction to Graph Theory, Pearson Education Inc., 2001.
[35] Information System on Graph Classes and their Inclusions, http://www.graphclasses.org/smallgraphs.
IJSER Β© 2015 http://www.ijser.org