07-11-2016, 10:42 AM
1465884141-IRN.docx (Size: 180.92 KB / Downloads: 6)
Abstract:
Alliance structure plays a vital role in social networks and it is used to study the important characteristic of similarity networks in natural and unnatural objects.For studying the co-alliance set we introduced the rebellion concept in [1], by interchanging the inequalities in the alliance set.In this paper, we study the independent property of the rebellion set and defined an independent rebellion number for simple graphs.In particular, we found the tight bounds an independent rebellion number and obtained the relationship between other rebellion parameters.
Keywords
Rebellion number, strong rebellion number, global rebellion number, total rebellion number and independent rebellion number.
AMS (MOS) SUBJECT CODES: 05C38,05C69
INTRODUCTION
A graph is a finite undirected connected simple graph with p vertices and q edges.All the terms defined here are used in the sense of Harary.Alliance in graphs was first introduced by Kristiansen, Hedetniemi and Hedetniemi in [5]. The global (strong) defensive alliance and its number were introduced and their bounds are studied in [6]. The alliance numbers for planar graphs are introduced in [7]. The domination, accurate domination and accurate total domination for simple graphs are referred from [2] and [4]. In paper[1] we introduced the rebellion set, strong rebellion set, global rebellion set, total rebellion set.A set R ⊆ V of a graph G = (V, E) is said to be a ‘rebellion set’(reb set) of G, if │N_R(v) │ ≤ │N_(V\R) (v) │, v∈R and . The rebellion number rb(G) is the minimum cardinality of any rebellion set in G. A rebellion set with cardinality rb(G) is denoted by rb(G) - set.A set R ⊆ V of a graph
G = (V, E) is said to be a ‘strong rebellion set’(srb – set) of G, if │N_R(v) │<│N_(V\R) (v) │, v∈R and . The strong rebellion number rbs(G) is the minimum cardinality of any strong rebellion set in G. A strong rebellion set with cardinality rbs (G) is denoted by rbs (G) – set.A rebellion set R of a graph G said to be global rebellion set (grb – set), if R is a dominating set of G. The global rebellion number rbg(G)is the minimum cardinality of any global rebellion set in G. A global rebellion set with cardinality rbg(G) is denoted by rbg(G) – set.A set R ⊆ V of a graph is said to be a ‘total rebellion set’(trb – set) of G, if │N_R(v) │≤ │N_(V\R) (v) │, v∈R and . The total rebellion number rbt(G) is the minimum cardinality of any total rebellion set in G. A total rebellion set with cardinality rbt(G) is denoted by rbt(G) – set.In this paper, we have introducedindependent rebellion number and maximum independent rebellion number. Also, we determined its tight bounds for some standard graph and characterise this parameters.
II. MAIN RESULT
Definition 2.1
A set R ⊆V of a graph is said to be an ‘independent rebellion set’(irb-set) of G, if │N_R(v) │ ≤ │N_(V\R) (v) │, v∈R , and no two vertices in R are adjacent. The independent rebellion number is the minimum cardinality of any independent rebellion set in G. An independent rebellion set with cardinality is denoted by - set.
Definition 2.2
The maximum independent rebellion number is the maximum cardinality of any independent rebellion set in G. The maximum independent rebellion set with cardinality is denoted by - set.
Example 2.3
G
figure 2.1
irb-set ={v1, v3, v4, v5, v6}, irb(G)= 5
Irb-set={v1, v3, v4, v5, v6, v7, v9}, Irb (G)= 7
Theorem 2.4
For the path graph Pn, n ≥ 2, =
Proof:
Let be the path graph with atleast two vertices with and
and R be an irb-set of G. The set is an
irb-set of G.Since R satisfies all the three conditions ofirb-set,
we have ≤ = … (1)
Let R be a irb(G)-set of G.Since and has only independent vertices
gives R must contain atleast vertices.Hence = ≥ … (2)
From (1) and (2), = .
For example
s
P7
figure
irb-set= {v1, v3, v5, v7, v9,}, irb(P7) = 5
Theorem 2.5
For the cycle graph Cn, ,n ≥ 4 and n is even.
Proof:
Let be the cycle graph with atleast four vertices with and and R be an irb-set of G. The set is an irb-set of G.Since R satisfies all the three conditions of irb-set.We have ≤ = … (1)