I. Sahul Hamid^a , S. Balamurugan^b , A. Navaneethakrishnan^c

sahulmat@yahoo.co.in, balamaths@rocketmail.com, snt.voc@gmail.com

A set S of vertices of a graph G such that hSi has an isolated vertex is called an isolate set of G. The minimum and maximum cardinality of a maximal isolate set are called the isolate number i0(G) and the upper isolate number I0(G) respectively. An isolate set that is also a dominating set (an irredundant set) is an isolate dominating set (an isolate irredundant set). The isolate domination number γ0(G) and the upper isolate domination number Γ0(G) are respectively the minimum and maximum cardinality of a minimal isolate dominating set while the isolate irredundance number ir0(G) and the upper isolate irredundance number IR0(G) are the minimum and maximum cardinality of a maximal isolate irredundant set of G. The notion of isolate domination was introduced in [5] and the remaining were introduced in [4]. This paper further extends a study of these parameters.

Keywords: isolate domination, isolate irredundant set Mathematics Subject Classification : 05C15 DOI:10.5614/ejgta.2016.4.1.8

1. Introduction

By a graph G = (V, E), we mean a finite, non-trivial, undirected graph with neither loops nor multiple edges. For graph theoretic terminology we refer to the book by Chartrand and Lesniak [2].

The open neighbourhood N(v) of a vertex is the set of all vertices adjacent to v while the closed neighbourhood N[v] is N(v) ∪ {v}. The subgraph induced by a set S of vertices of a graph

Received: 2 March 2015, Revised: 7 January 2016, Accepted: 14 March 2016.

^aDepartment of Mathematics, The Madura College, Madurai - 625 011, India

^bDepartment of Mathematics, St. Xavier's College, Palayamkottai - 627 002, India

^cDepartment of Mathematics, V.O.C College, Tuticorin-628 008, India

G is denoted by hSi with V (hSi) = S and E(hSi) = {uv ∈ E(G) : u, v ∈ S}. A vertex u is said to be a private neighbour of a vertex v ∈ S with respect to the set S if N[u] ∩ S = {v} (In particular, an isolated vertex in hSi 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 set D 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 minimal 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) equals the minimum cardinality of a total dominating set of G. A set D ⊆ V (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 cardinality of a maximal irredundant set are respectively called the irredundance number ir(G) and the upper irredundance number IR(G).

A set S of vertices of a graph G such that hSi has an isolated vertex is called an isolate set of G. The minimum and maximum cardinality of a maximal isolate set are called the isolate number i0(G) and the upper isolate number I0(G). An isolate set that is also a dominating set (an irredundant set) is an isolate dominating set (an isolate irredundant set). The isolate domination number γ0(G) and the upper isolate domination number Γ0(G) are respectively the minimum and maximum cardinality of a minimal isolate dominating set while the isolate irredundance number ir0(G) and the upper isolate irredundance number IR0(G) are the minimum and maximum cardinality of a maximal isolate irredundant set of G. An isolate set S of G with |S| = i0(G) is called an i0-set of G. Similarly, γ0-set, Γ0-set, ir0-set are defined. The notion of isolate domination was introduced in [5] and the remaining were introduced in [4]. An extended chain of inequalities connecting all these parameters has been established in [4] as below:

\[ir(G) \le ir_0(G) \le \gamma_0(G) \le i(G) \le \beta_0(G) \le \Gamma_0(G) = \Gamma(G) \le IR_0(G) = IR(G) \le I_0(G)\] (1)

This paper further studies these concepts by establishing some relationship among those parameters. We need the following results.

Theorem 1.1 ([4]). Let S be an isolate set of a graph G. Then, S is a maximal isolate set of G if and only if every vertex in V − S is adjacent to all the isolates of S.

Theorem 1.2 ([3]). If G is a graph of order n with no isolates, then γ(G) ≤ n 2 .

Theorem 1.3 ([1]). For any graph G, γ(G) ² ≤ ir(G) ≤ γ(G) ≤ 2ir(G) − 1.

Theorem 1.4 ([4]). Every minimal isolate dominating set of G is a maximal isolate irredudant set of G.

2. Main Results

In this section we establish some relationships among the isolate domination number and the isolate parameters ir⁰ and i0. We first obtain a bound for i⁰ in terms of order and characterizes the extremal graphs.

Theorem 2.1. For any graph G of order n, we have 1 ≤ i0(G) ≤ n. Further,

• (i) i0(G) = 1 if and only if ∆(G) = n − 1.
• (ii) i0(G) = 2 if and only if G = H + K2, where H is any graph with ∆(H) ≤ |V (H)| − 2.
• (iii) i0(G) = n if and only if G has an isolated vertex.
• Proof. (i) If ∆(G) = n − 1, then a vertex of degree n − 1 forms a maximal isolate set so that i0(G) = 1. On the other hand if {u} is a maximal isolate set of G, then every vertex of G other than u must be adjacent to u so that deg u = n − 1.
  • (ii) Suppose i0(G) = 2 and S is an i0-set of G. Then, S is an independent set of G and therefore by Theorem 1.1, we have every vertex of V − S is adjacent to both the vertices of S. Therefore G = K² + H, where H = hV − Si. Further, ∆(G) < |V (G)| − 1 as i0(G) > 1, and so ∆(H) < |V (H)| − 2. Conversely, if G = K² + H, where H is any graph with ∆(H) ≤ |V (H)| − 2, then i0(G) ≥ 2. Further, since the vertices of K² form a maximal isolate of G, the result follows.
  • (iii) If G itself has an isolated vertex, then V (G) is the only maximal isolate set of G so that i0(G) = n. Further, if i0(G) = n means V (G) is an isolate set so that there must be an isolated vertex.

The following theorems establish some relationships among the isolate parameters i0, ir⁰ and γ⁰ with global and total domination numbers.

Theorem 2.2. For any graph G, γt(G) ≤ i0(G) + 1 and the bound is sharp.

Proof. Let S be a maximal isolate set of G. Then, by Theorem 1.1, every vertex lying in V − S is adjacent to all the isolates of hSi and consequently for any vertex u ∈ V − S, the set S ∪ {u} is a total dominating set of G so that γt(G) ≤ i0(G) + 1. For stars, the value of γ^t is 2 whereas i⁰ equals 1.

Theorem 2.3. If diam G ≥ 5, then γg(G) ≤ γ0(G).

Proof. Let G be a graph of diameter at least 5 and let S be a γ0-set of G. Let us prove that S is a global dominating set of G. That is, we need to verify that S is a dominating set of G as well. It is clear that |S| ≥ 2 for otherwise diameter of G becomes two. Certainly, an isolated vertex of hSi will dominate all the vertices of S in G. Let us now see how the vertices of V − S are dominated in G by S. If a vertex v ∈ V − S is a private neighbour of a vertex u in S with respect to S, then it

will be dominated in \(\overline{G}\) by a vertex of S other than u (this is possible as \(|S| \geq 2\)). Therefore, only the vertices of V-S that are not private neighbours of any vertex of S have to be dominated in \(\overline{G}\) by S. Now, if there is a vertex in V-S that is adjacent to all the vertices of S in G, then that vertex will not be dominated in \(\overline{G}\) by any vertex of S. But we prove that this situation does not occur. Suppose in contrary that there is a vertex \(v \in V-S\) that is adjacent in G to all the vertices of S. Then for any two vertices \(u_1\) and \(u_2\) of G, we have the following cases.

• (i) If \(u_1, u_2 \in S\), then \((u_1, v, u_2)\) is a path connecting \(u_1\) and \(u_2\) and therefore \(d(u_1, u_2) \leq 2\).
• (ii) Let \(u_1, u_2 \in V S\) and \(u_1'\) and \(u_2'\) be the vertices in S adjacent to \(u_1\) and \(u_2\) respectively. If \(u_1 = u_2\), then \((u_1, u_1' = u_2', u_2)\) is a \(u_1 u_2\) path; otherwise \((u_1, u_1', v, u_2', u_2)\) is a path connecting \(u_1\) and \(u_2\) provided \(v \neq u_1, u_2\). Even if \(v = u_1\) then \((u_1 = v, u_2', u_2)\) is a required \(u_1 u_2\) path. Therefore \(d(u_1, u_2) \leq 4\).
• (iii) Let \(u_1 \in S\), \(u_2 \in V S\) and \(u_2'\) be a vertex in S dominating \(u_2\). Then \((u_1, v, u_2', u_2)\) will be a path connecting \(u_1\) and \(u_2\) and therefore \(d(u_1, u_2) \leq 3\).

Therefore the conclusion that we draw is any two vertices of G are at a distance of at most four so that \(diam\ G \le 4\) which is a contradiction to the assumption that \(diam\ G \ge 5\). Hence all the non-private neighbours of S in G are dominated in G by the vertices of S and so S is a dominating set of G also. Therefore \(\gamma_g(G) \le |S| = \gamma_0(G)\).

Remark 2.1. The above theorem need not be true for graphs of diameter less than five. For example, for the graphs of diameter 1 (complete graphs) the value of \(\gamma_g\) is its order whereas \(\gamma_0\) is just 1. The complete bipartite graph \(K_{r,s}\), where \(3 \leq r \leq s\), is of diameter two such that \(\gamma_0(K_{r,s}) = r\) and \(\gamma_g(K_{r,s}) = 2\). Further, graphs of diameter 3 and diameter 4 for which the value of \(\gamma_0\) exceeds the value of \(\gamma_g\) are given in Figure 1.

Figure 1. (a) A graph G of diameter 4 for which \(\gamma_0(G)=4<5=\gamma_g(G)\), (b) A graph H of diameter 3 for which \(\gamma_0(H)=3<4=\gamma_g(H)\)

Lemma 2.1. Let S be an \(i_0\)-set of a graph G. If there is a vertex in V-S that is adjacent to all the vertices of S, then diam \(G \leq 3\).

Proof. If \(i_0(G)=1\), then \(\Delta(G)=|V(G)|-1\) so that \(diam\ G\leq 2\). Assume \(i_0(G)\geq 2\). Let S be an \(i_0\)-set and v be a vertex in V-S that is adjacent to all the vertices of S. Therefore, two vertices of G that belong to S are at a distance of at most two. Now, if x is an isolate of \(\langle S \rangle\), it follows from Theorem 1.1 that every vertex in V-S is adjacent to all the isolates of \(\langle S \rangle\) and in particular to the vertex x and so any two vertices of G lying in V-S are at a distance of at most two. Suppose \(u_1\) and \(u_2\) are two vertices of G such that \(u_1 \in S\) and \(u_2 \in V-S\). If \(u_1=x\) or \(u_2=v\) then \(d(u_1,u_2)=1\), otherwise \((u_1,v,x,u_2)\) is an \(u_1-u_2\) path in G so that \(d(u_1,u_2)\leq 3\). Thus \(diam\ G\leq 3\).

Theorem 2.4. If diam \(G \geq 4\), then \(\gamma_q(G) \leq i_0(G)\).

Proof. Let G be a graph of diameter at least 4 and S be an \(i_0\)-set of G. Then an isolate of \(\langle S \rangle\) itself dominates all the vertices of V-S in G so that S is a dominating set of G by Theorem 1.1. Further, it follows from Lemma 2.1 that there is no vertex in V-S that is adjacent to all the vertices of V-S. That is, every vertex in V-S has a non-neighbour in S so that the vertices of V-S will be dominated in G by S. Certainly, an isolate of S dominates all the remaining vertices of S in G. Thus S is a global dominating set of S. Hence the desired result follows. \(\Box\)

The following theorem establishes an upper bound for \(\gamma_0\) in terms of \(i_0\) for \(C_4\)-free graphs with minimum degree at least 2.

Theorem 2.5. Let G be a \(C_4\)-free graph and \(\delta(G) \geq 2\). Then \(\gamma_0(G) \leq \left\lceil \frac{i_0(G)}{2} \right\rceil\) and the bound is sharp.

Proof. Let S be an \(i_0\)-set of G. We first claim that \(\langle S \rangle\) has exactly one isolated vertex. Suppose \(\langle S \rangle\) has more than one isolated vertices. Obviously, the set V-S must have at least two vertices; for otherwise the degree of the isolates of \(\langle S \rangle\) will be less than 2 which is not true as \(\delta(G) \geq 2\). Therefore \(|V-S| \geq 2\).

Figure 2. A \(C_4\)-free graph G with \(\delta(G)=2\) and \(\gamma_0(G)=\left\lceil \frac{i_o(G)}{2}\right\rceil\)

Now, by Theorem 1.1 that every isolate of \(\langle S \rangle\) is adjacent to all the vertices of V-S and so any two isolates of \(\langle S \rangle\) together with any two vertices of V-S will form a cycle of length 4. This is a contradiction and hence the claim follows. Therefore the set \(\langle S-\{v\}\rangle\) will have no isolated vertices, where v is the isolated vertex of S. By Theorem 1.2 that the cardinality of a \(\gamma\)-set D of \(\langle S-\{v\}\rangle\) is less than or equal to \(\frac{|S|-1}{2}\). Now, the isolated vertices of S together with the set D will form an isolate dominating set of S and hence S0 and hence S1. For the graph of Figure 2 the bound is attained.

Corollary 2.1. If G is a C4-free graph with δ(G) ≥ 2, then γ0(G) ≤ n−δ+1 2 .

Proof. The result follows from the fact that i0(G) ≤ n − δ.

Theorem 1.3 gives a bound for γ(G) in terms of ir(G). Similar to this, in the following theorem, we find an upper bound for γ0(G) in terms of ir0(G). It follows from Theorem 1.3 and Chain 1 that γ(G) ≤ 2ir(G) − 1 ≤ 2ir0(G) − 1. Thus we obtain a bound for γ(G) in terms of the isolate irredundance number ir0. The following theorem provides a similar result for γ0.

Theorem 2.6. For any graph G, γ0(G) ≤ 2(ir0(G) − 1).

Proof. Let ir0(G) = k and let S = {v1, v2, v3, . . . , v^t , vt+1, . . . , vk} be an ir0-set of G, where vt+1, vt+2, . . . , v^k are isolates of hSi. Since S is irredundant, pn[vⁱ , S] 6= φ, for 1 ≤ i ≤ k. Let S ⁰ = {u1, u2, . . . , ut} where uⁱ ∈ pn[vⁱ , S] for 1 ≤ i ≤ t. Now, we claim that the set S ⁰⁰ = S ∪ S 0 is an isolate dominating set of G. Since vt+1, vt+2, . . . v^k are the isolates of hS ⁰⁰i, it is enough to prove that S ⁰⁰ is a dominating set of G. If not, then there must be at least one vertex w ∈ V − S 00 which is not dominated by S ⁰⁰. This means that w /∈ N[x], for any vertex x ∈ S ⁰⁰ and therefore pn[w, S ∪ {w}] 6= φ. Hence the set S ∪ {w} is an isolate irredundant set which contradicts the assumption that S is a maximal irredundant set. Therefore S ⁰⁰ is an isolate dominating set. Even though S ⁰⁰ is an isolate dominating set it cannot be a minimal isolate dominating set; for otherwise by Theorem 1.4, it will be a maximal isolate irredundant set, which would again contradicts the maximality of S. Therefore γ0(G) ≤ |S ⁰⁰| − 1 ≤ 2(ir0(G) − 1).

3. Open Problems

We close the paper with the following interesting problems.

• (i) Find a class of graphs for which all the parameters in the chain 1 are distinct.
• (ii) It is proved in Theorem 2.2 that γt(G) ≤ i0(G) + 1. Find a characterization of graphs for which γt(G) = i0(G) + 1.
• (iii) The problem of characterizing ^C4-free graphs ^G with ^δ(G) ^{≥ 2} for which ^γ0(G) = ^l i0(G) 2 m seems to be challenging.

Acknowledgement

The work reported here is supported by the Project SR/FTP/MS-002/2012 awarded to the first author by the Department of Science and Technology, Science and Engineering Research Board, Government of India, New Delhi.

References

• [1] B. Bollobas and E.J. Cockayne, Graph theoretic parameters concerning domination, independence and irredundance, J. Graph Theory 3 (1979), 241-250.
• [2] G. Chartrand and Lesniak, Graphs and Digraphs, Fourth edition, CRC press, Boca Raton, 2005.
• [3] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of domination in Graphs, Marcel Dekker, New York (1998).
• [4] I. Sahul Hamid and S. Balamurugan, Extended Chain of Domination Parameters in Graphs, ISRN Combinatorics, volume 2013, Article ID 792743, 4 pages.
• [5] I. Sahul Hamid and S. Balamurugan, Isolate Domination in Graphs, Arab Journal of Mathematical Sciences, DOI:10.1016/j.ajmsc.2015.10.001.
• [6] I. Sahul Hamid and S. Balamurugan, Isolate domination in Unicyclic graphs International Journal of Mathematics and Soft Computing 3 (3) (2013), 79-83.
• [7] I. Sahul Hamid and S. Balamurugan, Isolate Domination Number and Maximum degree, Bulletin of the International Mathematical Virtual Institute 3 (2013), 127-133.