# Extended Chain of Domination Parameters in Graphs

Authors: I. Sahul Hamid; S. Balamurugan
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

A subsetS of the vertex set V(G) of a graph G is called an isolate set if the subgraph induced by S has an isolated vertex. The subset S is called an isolate dominating set if it is both isolate and dominating. Also, S is called an isolate irredundant set if it is both isolate and irredundant. In this paper, we establish a chain connecting various isolate parameters with the existing domination parameters and discuss equality among the parameters in the extended chain.


---

## Body

## 1. Introduction

One of the fastest growing areas within graph theory is the study of domination and related subset problems such as independence, covering, and matching. In fact, there are scores of graph theoretic concepts involving domination, covering, and independence. The bibliography in domination maintained by Haynes et al. [1] has over 1200 entries in which one can find an appendix listing 75 different types of domination and domination related parameters which have been studied in the literature. Hedetneimi and Laskar [2] edited the recent issue of discrete mathematics devoted entirely to domination, and a survey of advanced topics in domination is given in the book by Haynes et al. [3]. In 1978, Cockayne et al. [4] first defined what has now become a well-known inequality chain of domination related parameters of a graph G as follows:
(1)ir(G)≤γ(G)≤i(G)≤β0(G)≤Γ(G)≤IR(G),
where ir(G) and IR(G) denote the lower and upper irredundance numbers, γ(G) and Γ(G) denote the lower and upper domination numbers, and i(G) and β0(G) denote the independent domination number and independence number of a graph G, respectively. Since then, more than 100 research papers have been published in which this inequality chain is the focus of study. More specifically, extending this chain in either side by some fundamental domination parameters is one such direction of research. By fundamental domination parameter, we mean that they can be defined for all nontrivial connected graphs. Following this we introduced such a new variation of domination in the name of isolate domination of graphs. By isolate dominating set of G, we mean a dominating set S of G such that δ(〈S〉)=0, that is 〈S〉, has an isolated vertex, and the corresponding parameters γ0 and Γ0 are, respectively, the minimum and maximum cardinalities of a minimal isolate dominating set of G. The study of this new variation of parameter was initiated in [5], where the existing domination chain (1) was extended as follows:
(2)ir(G)≤γ(G)≤γ0(G)≤i(G)≤β0(G)≤Γ0(G)≤Γ(G)≤IR(G).This paper extends the above chain with the addition of some new variates related to isolate domination and discusses the relationship among some of the parameters involved in this new chain.


## 2. Definitions, Notations, and Preliminary Results

By a GraphG=(V,E), we mean a finite, nontrivial, undirected graph with neither loops nor multiple edges. For graph theoretic terminology, we refer to the book by Chartrand and Lesniak [6].In a GraphG=(V,E), the open neighbourhood of a vertex v∈V is N(v)={u∈V:(u,v)∈E(G)}, and the closed neighbourhood is N[v]=N(v)∪{u}. The subgraph induced by a set S of vertices of a graph G is denoted by 〈S〉 with V(〈S〉)=S and E(〈S〉)={(u,v)∈E(G):u,v∈S}. A vertex u is said to be a private neighbour of a vertex v with respect to the set S if N[u]∩S={v} (in particular, an isolated vertex in 〈S〉 is a private neighbour of itself with respect to the set S). The private neighbour set of a vertex v with respect to the set S is denoted by pn[v,S].A setD of vertices of a graph G is said to be a dominating set if every vertex in V-D is adjacent to a vertex in D. A dominating set D is said to be a minimal dominating set if no proper subset of D is a dominating set. The minimum cardinality of a dominating set of a graph G is called the domination number of G and is denoted by γ(G). The upper domination numberΓ(G) is the maximum cardinality of a minimal dominating set of G. The minimum cardinality of an independent dominating set is called the independent domination number denoted by i(G), and the independence numberβ0(G) is the maximum cardinality of an independent set of G. A set S is a total dominating set, if N(S)=V. The total domination numberγt(G) is equal to the minimum cardinality of a total dominating set of G. A set G which is a dominating set of both G and G¯ is called a global dominating set. The minimum cardinality of a global dominating is called the global domination number and is denoted by γg(G). A set S of vertices is irredundant if every vertex v∈S has at least one private neighbour. The minimum and maximum cardinalities of a maximal irredundant set are, respectively, called their redundance numberir(G) and the upper irredundance numberIR(G). If p is one of these parameters, then by a p(G)-set, we mean a subset of V(G) having cardinality p(G) and the appropriate graphical property. If the graph G is clear from the context, then we will refer simply to a p-set.The following theorems are required for the subsequent sections.Theorem 1 (see [5]).
Every minimal isolate dominating set is a minimal dominating set.Theorem 2 (see [1]).
Every minimal dominating set in a graphG is a maximal irredundant set of G.Theorem 3 (see [1]).
A dominating setD is a minimal dominating set if and only if for each vertex u in D, one of the following conditions holds.  (i)
uis an isolate of 〈D〉.(ii)
There exists a vertexv in V-D, for which N(v)∩D={u}.Theorem 4 (see [1]).
If graphG has no isolated vertices, then γ(G)≤n/2.


## 3. Integrated Chain

As mentioned in the introduction, we introduce some new variants related to isolate domination and extend the dominating chain (2).Definition 5.
A setS⊆V(G) of a graph G whose induced subgraph has an isolate is called an isolate set, and the isolate numberi0(G) and the upper isolate numberI0(G) are defined to bei0(G) = Min {|S|:S is a maximal isolate set of G},I0(G) = Max {|S|:S is a maximal isolate set of G}.Further, an irredundant set which is also an isolate set is called anisolate irredundant set of G. The minimum and the maximum cardinalities of a maximal isolate irredundant set of a graph G are, respectively, called the isolate irredundancenumber  ir0(G) and the upper isolate irredundancenumber  IR0(G).Theorem 6.
Every minimal isolate dominating set is a maximal isolate irredundant set.Proof.
The result follows from Theorems1 and 2.Corollary 7.
For any graphG, ir0(G)≤γ0(G)≤Γ0(G)≤IR0(G).Theorem 8.
LetS be an isolate set of a graph G. Then, S is a maximal isolate set if and only if every vertex in V-S is adjacent to all the isolates of S.Proof.
LetS be a maximal isolate set of G. If there is a vertex v∈V-S such that N(v) does not contain an isolate of S, then S∪{v} will be an isolate set of G containing S. This contradicts the maximality of S, and hence the result follows. The converse part is obvious.Now, it is obvious from the above theorem that every maximal isolate set is an isolate dominating set, and soγ0(G)≤i0(G). Also, as I0(G) is the maximum cardinality of an isolate set of G, we have IR0(G)≤I0(G). Of course, ir(G)≤ir0(G), and then we get the following chains of inequalities:
(3)ir(G)≤ir0(G)≤γ0(G)≤i0(G),(4)Γ0(G)≤IR0(G)≤I0(G).Theorem 9.
For any graphG, i(G)≤i0(G), and the bound is sharp.Proof.
Consider ani0-set of G, and let I be the set of all isolates of S. From the graph 〈S-I〉, choose one of its independent dominating set, say S1. Then S1∪I is obviously an independent set of G. By Theorem 8, vertices of G lying in V-S are dominated even by a single vertex in I. As S1 dominates all the vert ces in S-I, the set S1∪I is a dominating set of G, and consequently it is an independent dominating set of G. Hence, the desired inequality follows.Further, since ani-set is a minimal isolate dominating set of a graph G, we have γ0(G)≤i(G), and so the Chain (3) is extended as follows:
(5)ir(G)≤ir0(G)≤γ0(G)≤i(G)≤i0(G).As in the chains (2) and (4), each of the parameters γ and ir0 lies between ir and γ0. However, there is no relation between ir0 and γ. In fact, we can prove that the difference between γ and ir0 can be arbitrarily large which is shown in the following theorem. It is noted that γ(G)≤2ir(G)-1≤2ir0(G)-1. Thus, the value of γ(G) can be at most 2ir0(G)-1.Theorem 10.
(
i
) For given positive integers a and b such that a≤b, there exists a graph G such that γ(G)=a and ir0(G)=b.
(
ii
) If a and b are any two integers such that b≤a≤2b-1, then there exists a graph G such that γ(G)=a and ir0(G)=b.Proof.
(
i
) Let G=H∘tK1, where t=b-a+1 and H is any connected graph of order a. Then, obviously γ(G)=a. Now, as H is a connected graph, any isolate irredundant set of G must omit at least one vertex of H, and consequently the corresponding pendant vertices have to be selected. Thus, ir0(G)≥|V(H)|-1+b-a+1=b. Now, one can easily obtain an ir0-set of cardinality b, we have ir0(G)=b.
(
ii
) Let P=(v1,v2,…,vb) be a path on b vertices. Now, attach at least two pendant vertices at each of vi, i≠b-1, and then join all the pendant vertices of vi with a vertex ui, for i=1 to a and let the resultant graph be G. Now, one can easily verify that ir0(G)=b and γ(G)=2b-1.We find that for any graphG, the value of I0 is n-δ, and also the parameters Γ0 and IR0 coincide with the existing domination parameters Γ and IR, respectively, as shown below.Theorem 11.
For any graphG, one has Γ(G)=Γ0(G), IR0(G)=IR(G), and I0(G)=n-δ.Proof.
As in Theorem1, a minimal isolate dominating set is a minimal dominating set, and consequently by the definitions of Γ(G) and Γ0(G), it follows that Γ0(G)≤Γ(G), for any graph G. So, we need to verify only the other inequality. For this, consider a Γ-set S of G. Of course, the set S need not be an isolate dominating set; however, we can construct a minimal isolate dominating set of cardinality more than or equal to that of S as follows. Choose a vertex v in S arbitrarily, and let S1 be any minimal isolate dominating set of 〈pn[v,S]〉. Thus, the set S=(S-{v})∪S1 is an an isolate dominating of G (note that the vertices that are isolates with respect to S1 are isolates with respect to S as well). Minimality of S′ with respect to isolate domination follows from the minimality of S1 (with respect to isolate domination) and the minimality of S (with respect to domination).
LetD be an IR-set of G. If 〈D〉 has an isolated vertex then the proof is completed; otherwise, every vertex in D has a private neighbour in V-D. Now, the reader can easily observe that for a vertex v∈D, the set (D-{v})∪T, where T is an IR0 set of 〈pn[v,D]〉, forms an isolate irredundant set of G. As IR0(〈pn[v,D]〉)≥1, for every v∈D, |D-{v}∪T|≥|D|, and therefore IR(G)≤|D-{v}∪T|≤IR0(G). Since IR(G) is the maximum cardinality of an irredundant set of G, IR0(G)≤IR(G).
Since for any vertexv of a graph G, V(G)-N(v) is an isolate set of G, it follows that I0(G)≥Maxv∈V(G)|V(G)-N(v)|=n-δ. Further, if S is an isolate set, then all the neighbours of an isolated vertex of S lie outside S, and consequently |S|≤n-δ so that I0(G)≤n-δ. Thus, for any graph G, the value of I0(G) is always n-δ.Now, let us try to form a unified chain connecting all the domination and isolate parameters.(6)ir(G)≤ir0(G)≤γ0(G)≤i(G)≤β0(G)≤Γ0(G)=Γ(G)≤IR0(G)=IR(G)≤I0(G).For complete multipartite graphs in which all the parts are of same cardinality and in particular for complete graphs, all the above parameters are equal.


## 4. Equality of Parameters

Theorem 12.
If eitherδ(G)=0 or Δ(G)=n-1, then γ(G)=γ0(G), where n is the order of G.Proof.
Obviously, whenδ(G)=0, the isolated vertices of G will be in every γ-set of G, and hence γ=γ0. Also when Δ(G)=n-1, γ(G)=1, and hence the result follows.Theorem 13.
For a generalised Petersen graphG, γ(G)=γ0(G).Proof.
LetS be a γ-set of G. If 〈S〉 has an isolated vertex then we are through. Now, we assume that 〈S〉 has no isolated vertices. Then, every vertex of S will have at least one private neighbour. Further, it can be observed that the cardinality of S will be minimum when each vertex of S has exactly two private neighbours and also in that case, |S|=n/3. Now, we assert that there is an isolate dominating set for G with cardinality less than n/3. By bearing in mind the usual structure of the generalised Petersen graph, we label the vertices of the outer circle as u1, u2,…,un/2 and the inner circle as v1, v2,…,vn/2 such that (ui,vi)∈E(G), for every i. Now, the set S′={u1,v3,u5,v7,…}, where the last vertex of S′ belongs to the set {un/2, un/2-1, vn/2, vn/2-1}, forms an isolate dominating set of G. Since |S′|=⌈n/4⌉≤n/3.Theorem 14.
IfG does not contain an induced C4, then γ0(G)=ir0(G) and Γ0(G)=IR0(G).Proof.
LetS be a maximal isolate irredundant set of G. If every vertex in V-S is adjacent to a vertex in S, then S becomes an isolate dominating set of G. Further, as every vertex in S has a private neighbour in V-S, S is a minimal isolate dominating set of G, and hence we are through. Now, suppose there is a vertex v in V-S which is not adjacent to any vertex in S. Then pn[u,S]⊆N(v), for some u in S; otherwise, S∪{v} would become an isolate irredundant set of G, contradicting the maximality of S. At this juncture, it is needless to say that u cannot be an isolate of S (if u is an isolate of S then u∈pn[u,S]⊆N(v) and therefore (u,v)∈E(G)). Now, let us claim that 〈pn[u,S]〉 is a complete graph. For any two vertices u1 and u2 of pn[u,S], 〈{u,u1,u2,v}〉 cannot be a C4 and also (u,v)∉E(G). Hence, (u1,u2)∈E(G), and consequently our claim follows. Now, the set S′={vi∈pn[ui,S]/ui is a nonisolate of S}∪S1, where S1 is the set of isolates of S, forming an isolate dominating set of G. Further, every vi∈S′-S1, has a private neighbour with respect to S′, and also a vertex in S1, being isolate with respect to S′, is a private neighbour of itself. Thus, S′ is minimal with respect to being isolate domination. Hence, γ0(G)≤ir0(G), and IR0(G)≤Γ0(G).Corollary 15.
For any treeT, γ0(T)=ir0(T), and Γ0(T)=IR0(T).Theorem 16.
Ifγ0(G)=i0(G), then every γ0-set of G is an independent dominating set.Proof.
Letγ0=i0 and v be an isolate in an i0-set I of G. Then, v would dominate all the vertices of V-I. If there is an edge (u,v) in 〈I〉, then I-{u} would become an isolate dominating set of cardinality γ0-1. This is a contradiction, and therefore I must be an independent set, and consequently by Theorem 8 every vertex of I is adjacent to all the vertices of V-I and conversely. Hence, for any γ0-set S of G, either S⊆I or S⊆V-I. If the first case happened, there is nothing to prove. Now, suppose that  S⊆V-I and (u,v) is an edge in S, then S-{u} would be an isolate dominating set of cardinality less than γ0 and hence the theorem.Remark 17.
The converse of the above theorem is not true. For example, for the pathP(v1,v2,…,v6) on six vertices, {u2, u5} is the only γ0-set which is independent, but i0=4.Theorem 18.
For any complete multipartite graphG, γ0(G)=ir0(G)=i(G)=i0(G).Proof.
LetS be any γ0-set of G. Since the parts of G are the only minimal isolate dominating sets, S must be a part of minimum cardinality. Being a part of G, all the vertices of S are isolates, and every vertex in S is adjacent to all the vertices of V-S. Hence, by Theorem 8, S is a maximal isolate set of G, and so i0(G)≤γ0(G).



---

*Source: 792743-2013-09-26.xml*