Revision as of 13:03, 16 September 2016 (view source) Clara (talk | contribs) (Created page with "==Abstract== A set <math display="inline">D</math> of vertices of a graph <math display="inline">G</math> is called a ''dominating set  '' of <math display="inline">G</math>...")	Latest revision as of 15:38, 7 October 2016 (view source) Vican (talk | contribs) m (Vican moved page Draft García 566045029 to Sahul-Hamid Balamurugan 2015a)
(No difference)

---

Latest revision as of 15:38, 7 October 2016

Abstract

A set ${\textstyle D}$ of vertices of a graph ${\textstyle G}$ is called a dominating set   of ${\textstyle G}$ if every vertex in ${\textstyle V(G)-D}$ is adjacent to a vertex in ${\textstyle D}$. A dominating set ${\textstyle S}$ such that the subgraph ${\textstyle \left\langle S\right\rangle }$ induced by ${\textstyle S}$ has at least one isolated vertex is called an isolate dominating set. An isolate dominating set none of whose proper subset is an isolate dominating set is a minimal isolate dominating set. The minimum and maximum cardinality of a minimal isolate dominating set are called the isolate domination number  ${\textstyle \gamma _{0}}$ and the upper isolate domination number  ${\textstyle \Gamma _{0}}$ respectively. In this paper we initiate a study on these parameters.

2010 Mathematics Subject Classification

059C

Keywords

Dominating set; Isolate dominating set; Isolate domination number; Upper isolate domination number

1. Introduction

By a graph, we mean a finite, undirected graph with neither loops nor multiple edges. For graph theoretic terminology we refer to the book by Chartrand and Lesniak  [2]. All graphs in this paper are assumed to be non-trivial.

In a graph ${\textstyle G=(V,E)}$, the degree   of a vertex ${\textstyle v}$ is defined to be the number of edges incident with ${\textstyle v}$ and is denoted by ${\textstyle degv}$. The minimum of ${\textstyle \lbrace degv:v\in V(G)\rbrace }$ is denoted by ${\textstyle \delta (G)}$ and the maximum of ${\textstyle \lbrace degv:v\in V(G)\rbrace }$ is denoted by ${\textstyle \Delta (G)}$. The open neighbourhood   of a vertex ${\textstyle v\in V(G)}$ is ${\textstyle N(v)=\lbrace u\in V(G):uv\in E(G)\rbrace }$ and the closed neighbourhood   is ${\textstyle N[v]=N(v)\cup \lbrace v\rbrace }$. The subgraph induced by a set ${\textstyle S}$ of vertices of a graph ${\textstyle G}$ is denoted by ${\textstyle \left\langle S\right\rangle }$ with ${\textstyle V(\left\langle S\right\rangle )=S}$ and ${\textstyle E(\left\langle S\right\rangle )=\lbrace uv\in E(G):u,v\in S\rbrace }$. For a set ${\textstyle S}$ of vertices, a vertex ${\textstyle v}$ is said to be a private neighbour   of a vertex ${\textstyle u\in S}$ with respect to ${\textstyle S}$ if ${\textstyle N[v]\cap S=\lbrace u\rbrace }$. Furthermore, we define the private neighbour set   of ${\textstyle u}$, with respect to ${\textstyle S}$, to be ${\textstyle pn[u,S]=\lbrace v:N[v]\cap S=\lbrace u\rbrace \rbrace }$. Notice that ${\textstyle u\in pn[u,S]}$ if ${\textstyle u}$ is an isolate in ${\textstyle \left\langle S\right\rangle }$, in which case we say that ${\textstyle u}$ is its own private neighbour. A vertex cover   in a graph ${\textstyle G}$ is a set of vertices that covers all the edges of ${\textstyle G}$. The minimum number of vertices in a vertex cover of ${\textstyle G}$ is called the vertex covering number   and is denoted by ${\textstyle \alpha _{0}(G)}$. If ${\textstyle G}$ and ${\textstyle H}$ are disjoint graphs, then the join   of ${\textstyle G}$ and ${\textstyle H}$ denoted by ${\textstyle G+H}$ is the graph such that ${\textstyle V(G+H)=V(G)\cup V(H)}$ and ${\textstyle E(G+H)=E(G)\cup E(H)\cup \lbrace uv:u\in V(G),v\in V(H)\rbrace }$. A wheel   on ${\textstyle n}$ vertices (${\textstyle n\geq 4}$), denoted by ${\textstyle W_{n}}$, is the graph ${\textstyle K_{1}+C_{n-1}}$. The vertex corresponding to ${\textstyle K_{1}}$ is called the centre vertex   of ${\textstyle W_{n}}$. The corona   of two disjoint graphs ${\textstyle G_{1}}$ and ${\textstyle G_{2}}$ is defined to be the graph ${\textstyle G=G_{1}\circ G_{2}}$ formed from one copy of ${\textstyle G_{1}}$ and ${\textstyle \vert V(G_{1})\vert }$ copies of ${\textstyle G_{2}}$ where the ${\textstyle i}$th vertex of ${\textstyle G_{1}}$ is adjacent to every vertex in the ${\textstyle i}$th copy of ${\textstyle G_{2}}$.

The study of domination and related subset problems is one of the fastest growing areas in graph theory. For a detailed survey of domination one can see  [5] and [6] and  [7]. A set ${\textstyle D}$ of vertices of a graph ${\textstyle G}$ is said to be a dominating set   if every vertex in ${\textstyle V-D}$ is adjacent to a vertex in ${\textstyle D}$. A dominating set ${\textstyle D}$ is said to be a minimal dominating set   if no proper subset of ${\textstyle D}$ is a dominating set. The minimum cardinality of a dominating set of a graph ${\textstyle G}$ is called the domination number   of ${\textstyle G}$ and is denoted by ${\textstyle \gamma (G)}$. The upper domination number  ${\textstyle \Gamma (G)}$ is the maximum cardinality of a minimal dominating set of ${\textstyle G}$. The minimum cardinality of an independent dominating set is called the independent domination number  , denoted by ${\textstyle i(G)}$ and the independence number  ${\textstyle \beta _{0}(G)}$ is the maximum cardinality of an independent set of ${\textstyle G}$. A set ${\textstyle S}$ of vertices is irredundant   if every vertex ${\textstyle v\in S}$ has at least one private neighbour with respect to ${\textstyle S}$. The minimum and maximum cardinalities of a maximal irredundant set are respectively called the irredundance number  ${\textstyle ir(G)}$ and the upper irredundance number  ${\textstyle IR(G)}$. An inequality chain connecting these parameters was established in  [3] as given below.

${\displaystyle ir(G)\leq \gamma (G)\leq i(G)\leq \beta _{0}(G)\leq \Gamma (G)\leq IR(G){\mbox{.}}}$

(1)

A detailed survey of results about this domination chain can be seen in  [6] wherein it has been suggested that extending this chain by means of parameters whose values lie between any two consecutive parameters in the chain is one direction of research. This paper introduces such a domination parameter namely isolate domination number and upper isolate domination number which are defined as follows.

A dominating set ${\textstyle S}$ of a graph ${\textstyle G}$ is said to be an isolate dominating set   of ${\textstyle G}$ if ${\textstyle \left\langle S\right\rangle }$ has at least one isolated vertex. An isolate dominating set ${\textstyle S}$ is said to be a minimal isolate dominating set   if no proper subset of ${\textstyle S}$ is an isolate dominating set. The minimum and maximum cardinality of a minimal isolate dominating set of ${\textstyle G}$ are called the isolate domination number  ${\textstyle \gamma _{0}(G)}$ and the upper isolate domination number  ${\textstyle \Gamma _{0}(G)}$ respectively. An isolate dominating set of cardinality ${\textstyle \gamma _{0}}$ is called a ${\textstyle \gamma _{0}}$-set. Similarly, the sets ${\textstyle \gamma }$-set, ${\textstyle \Gamma }$-set and ${\textstyle \Gamma _{0}}$-set are defined. Obviously, every independent dominating set in a graph is an isolate dominating set so that every graph possess an isolate dominating set as every graph has an independent dominating set. Hence the property being isolate domination is fundamental.

This paper initiates a study on these parameters isolate domination number ${\textstyle \gamma _{o}}$ and the upper isolate domination number ${\textstyle \Gamma _{0}}$. More specifically, the exact values of ${\textstyle \gamma _{0}}$ and ${\textstyle \Gamma _{0}}$ for some common classes of graphs such as paths, cycles, wheels and complete multipartite graphs are determined in Section  2. As an important result it is proved in Section  3 that the parameters ${\textstyle \gamma _{0}}$ and ${\textstyle \Gamma _{0}}$ got fit into the domination chain 1 and consequently an extended domination chain has been established. Further, some bounds for ${\textstyle \gamma _{0}}$ and ${\textstyle \Gamma _{0}}$ have been discussed in terms of order, size, degree and covering number. Moreover, the parameter ${\textstyle \gamma _{o}}$ for cubic graphs is proved to be ${\textstyle \gamma }$ or ${\textstyle \gamma +1}$ and those cubic graphs for which ${\textstyle \gamma _{0}=\gamma +1}$ are also obtained. Finally, we conclude the paper with some open problems along with some directions for further research.

The following theorems are required in the subsequent sections.

Theorem 1.1 [6].

A dominating set  ${\textstyle D}$is a minimal dominating set if and only if for each vertex  ${\textstyle u}$in  ${\textstyle D}$, one of the following conditions holds.

• ${\textstyle u}$is an isolate of  ${\textstyle \left\langle D\right\rangle }$.
• There exists a vertex  ${\textstyle v}$in  ${\textstyle V-D}$, for which  ${\textstyle N(v)\cap D=\lbrace u\rbrace }$.

Theorem 1.2 [4].

For any graph G of order  ${\textstyle n}$,  ${\textstyle \Gamma (G)+\delta (G)\leq n}$.

Theorem 1.3 [6].

If  ${\textstyle G}$is a graph with no isolated vertices, then the complement  ${\textstyle V-S}$of every minimal dominating set  ${\textstyle S}$is a dominating set.

2. Exact values

In this section, we determine the value of isolate domination number and the upper isolate domination number for some standard graphs such as paths, cycles, complete multipartite graphs and wheels.

Proposition 2.1.

• For the paths  ${\textstyle P_{n}}$and the cycles  ${\textstyle C_{n}}$, we have  ${\textstyle \gamma _{0}(P_{n})=\gamma _{0}(C_{n})=\lceil {\frac {n}{3}}\rceil }$,  ${\textstyle \Gamma _{0}(P_{n})=\lceil {\frac {n}{2}}\rceil }$and  ${\textstyle \Gamma _{0}(C_{n})=\lfloor {\frac {n}{2}}\rfloor }$.
• For a complete k-partite graph  ${\textstyle G=K_{m_{1},m_{2},\ldots ,m_{k}}}$,  ${\textstyle \gamma _{0}(G)=Min\lbrace m_{1},m_{2},\ldots ,m_{k}\rbrace }$and  ${\textstyle \Gamma _{0}(G)=Max\lbrace m_{1},m_{2},\ldots ,m_{k}\rbrace }$. In particular,  ${\textstyle \gamma _{0}(K_{n})=\Gamma _{0}(K_{n})=1}$.
• For the wheel  ${\textstyle W_{n}}$on  ${\textstyle n}$vertices,  ${\textstyle \gamma _{0}(W_{n})=1}$and  ${\textstyle \Gamma _{0}(W_{n})=\lfloor {\frac {n-1}{2}}\rfloor }$.
• If  ${\textstyle G}$is a graph of order  ${\textstyle n}$, then  ${\textstyle \gamma _{0}(G^{+})=\Gamma _{0}(G^{+})=n}$, where  ${\textstyle G^{+}}$is the graph obtained from  ${\textstyle G}$by attaching exactly one edge at every vertex of  ${\textstyle G}$.

Proof.

• Obviously ${\textstyle \gamma _{0}(P_{4})=2}$ and when ${\textstyle n\not =4}$, any ${\textstyle \gamma }$-set of ${\textstyle P_{n}}$ is an isolate dominating set as well, so that ${\textstyle \gamma _{0}(P_{n})\leq \gamma (P_{n})}$. Of course, the other inequality is immediate so that ${\textstyle \gamma _{0}(P_{n})=\gamma (P_{n})}$ and so ${\textstyle \gamma _{0}(P_{n})=\lceil {\frac {n}{3}}\rceil }$ as ${\textstyle \gamma (P_{n})=\lceil {\frac {n}{3}}\rceil }$. Now, if ${\textstyle P_{n}=(v_{1},v_{2},v_{3},\ldots ,v_{n})}$ then the set ${\textstyle S=\lbrace v_{2i-1}/1\leq i\leq \lceil {\frac {n}{2}}\rceil \rbrace }$ is a minimal isolate dominating set so that ${\textstyle \Gamma _{o}(P_{n})\geq \lceil {\frac {n}{2}}\rceil }$. Further, as any set with more than ${\textstyle \lceil {\frac {n}{2}}\rceil }$ vertices of ${\textstyle P_{n}}$ can no longer be a minimal isolate dominating set, we have ${\textstyle \Gamma _{0}(P_{n})=\lceil {\frac {n}{2}}\rceil }$. In a similar way one can prove that ${\textstyle \gamma _{0}(C_{n})=\lceil {\frac {n}{3}}\rceil }$ and ${\textstyle \Gamma _{0}(C_{n})=\lfloor {\frac {n}{2}}\rfloor }$.
• It is quite obvious that the k-parts of ${\textstyle G}$ are the only minimal isolate dominating sets of ${\textstyle G}$ so that ${\textstyle \gamma _{0}(G)=Min\lbrace m_{1},m_{2},\ldots ,m_{k}\rbrace }$ and ${\textstyle \Gamma _{0}(G)=Max\lbrace m_{1},m_{2},\ldots ,m_{k}\rbrace }$. In particular ${\textstyle \gamma _{0}(K_{n})=\Gamma _{0}(K_{n})}$= 1.
• The centre vertex of ${\textstyle W_{n}}$ dominates all other vertices and therefore ${\textstyle \gamma _{0}(W_{n})=1}$. Also, an isolate dominating set containing the centre vertex never contains any other vertex of ${\textstyle W_{n}}$ as it ceases the formation of isolates. Therefore a minimal isolate dominating set of the wheel with maximum cardinality must avoid the centre vertex and consequently it would be a ${\textstyle \Gamma _{0}}$-set of the subgraph induced by the remaining vertices, which is obviously a cycle on ${\textstyle n-1}$ vertices. Hence the result follows from (i).
• Let ${\textstyle S}$ be any minimal isolate dominating set of ${\textstyle G^{+}}$. Then ${\textstyle S}$ must contain each pendant vertex or its neighbour so that ${\textstyle S}$ contains at least ${\textstyle n}$ vertices. Further, if ${\textstyle \vert S\vert >n}$, then ${\textstyle S}$ must contain a pendant vertex together with its support and so ${\textstyle S-\lbrace v\rbrace }$, where ${\textstyle v}$ is the support, is an isolate dominating set of ${\textstyle G^{+}}$, a contradiction to the minimality of ${\textstyle S}$. Hence ${\textstyle \vert S\vert =n}$. □

The following proposition determines the values of ${\textstyle \gamma _{0}(G)}$ and ${\textstyle \Gamma _{0}(G)}$ for a disconnected graph ${\textstyle G}$.

Proposition 2.2.

If  ${\textstyle G}$is a disconnected graph with components  ${\textstyle G_{1}}$,  ${\textstyle G_{2}}$, …,  ${\textstyle G_{r}}$, then

• ${\textstyle \gamma _{0}(G)=min_{1\leq i\leq r}\lbrace t_{i}\rbrace }$, where  ${\textstyle t_{i}=\gamma _{0}(G_{i})+\sum _{j=1,j\not =i}^{r}}$${\textstyle \gamma (G_{j})}$.
• ${\textstyle \Gamma _{0}(G)=max_{1\leq i\leq r}\lbrace s_{i}\rbrace }$, where  ${\textstyle s_{i}=\Gamma _{0}(G_{i})+\sum _{j=1,j\not =i}^{r}}$${\textstyle \Gamma (G_{j})}$.

Proof.

• Assume that ${\textstyle t_{1}=min\lbrace t_{1},t_{2},t_{3},\ldots ,t_{r}\rbrace }$. Let ${\textstyle S}$ be a ${\textstyle \gamma _{0}}$-set of ${\textstyle G_{1}}$ and let ${\textstyle D_{i}}$ be a ${\textstyle \gamma }$-set of ${\textstyle G_{i}}$ for all ${\textstyle i\geq 2}$. Then the set ${\textstyle S\cup (\bigcup _{i=2}^{r}D_{i})}$ is an isolate dominating set of ${\textstyle G}$ so that ${\textstyle \gamma _{0}(G)\leq \gamma _{0}(G_{1})+\sum _{j=2}^{r}\gamma (G_{j})=t_{1}=min_{1\leq i\leq r}\lbrace t_{i}\rbrace }$. Now, let ${\textstyle S}$ be a minimal isolate dominating set of ${\textstyle G}$. Then ${\textstyle S}$ must intersect the vertex set ${\textstyle V(G_{i})}$ of each component ${\textstyle G_{i}}$ and so ${\textstyle S\cap V(G_{i})}$ is a minimal dominating set of ${\textstyle G_{i}}$, for all ${\textstyle i=1}$ to ${\textstyle r}$. Further, at least one of the sets of ${\textstyle S\cap V(G_{i})}$, say ${\textstyle S\cap V(G_{j})}$, must be an isolate dominating set of ${\textstyle G_{j}}$. Therefore ${\textstyle \vert S\vert \geq \gamma _{0}(G_{j})+\sum _{i=1,i\not =j}^{r}\gamma (G_{i})=t_{j}\geq min_{1\leq i\leq r}\lbrace t_{i}\rbrace }$ and hence ${\textstyle \gamma _{0}(G)=min_{1\leq i\leq r}\lbrace t_{i}\rbrace }$.
• For every value of ${\textstyle i}$, a ${\textstyle \Gamma _{0}}$-set of ${\textstyle G_{i}}$ together with the set ${\textstyle \bigcup _{j=1,j\not =i}^{r}D_{j}}$, where ${\textstyle D_{j}}$ is a ${\textstyle \Gamma }$-set of ${\textstyle G_{j}}$, forms a minimal isolate dominating set of ${\textstyle G}$. Therefore ${\textstyle \Gamma _{0}(G)\geq max_{1\leq i\leq r}\lbrace \Gamma _{0}(G_{i})+\sum _{j=1,j\not =i}^{r}\Gamma (G_{j})\rbrace }$. Now, let ${\textstyle S}$ be any minimal isolate dominating set of ${\textstyle G}$. Then the set ${\textstyle S\cap V(G_{i})}$ is a minimal dominating set of ${\textstyle G_{i}}$ for every value of ${\textstyle i}$ and in particular ${\textstyle S\cap V(G_{i})}$ must be a minimal isolate dominating set for at least one value of ${\textstyle i}$, say ${\textstyle j}$. Then ${\textstyle \vert S\vert \leq \Gamma _{0}(G_{j})+\sum _{i=1,i\not =j}^{r}\Gamma (G_{i})=s_{j}\leq max_{1\leq i\leq r}\lbrace s_{i}\rbrace }$. □

3. Extended domination chain

Here we prove that the isolate domination parameters ${\textstyle \gamma _{0}}$ and ${\textstyle \Gamma _{0}}$ extend the existing domination chain (1) as shown below.

Proposition 3.1.

For any graph  ${\textstyle G}$, we have  ${\textstyle ir(G)\leq \gamma (G)\leq \gamma _{0}(G)\leq i(G)\leq \beta _{0}(G)\leq \Gamma _{0}(G)\leq \Gamma (G)\leq IR(G)}$.

Thus the new variation of domination namely the isolate domination is interesting as it is fundamental in the sense that it is defined for all graphs and extends the existing dominating chain (1). Let us now proceed to establish the above extended domination chain given in Proposition 3.1.

To start with, let us recall the terms minimality and 1-minimality of a set with respect to a graph theoretic property. Let ${\textstyle P}$ be an arbitrary property of a set of vertices in a graph ${\textstyle G}$. If a set ${\textstyle S}$ has property ${\textstyle P}$, then we say that ${\textstyle S}$ is a ${\textstyle P}$-${\textstyle set}$. A ${\textstyle P}$-set ${\textstyle S}$ is a 1-minimal     ${\textstyle P}$-set if for any vertex ${\textstyle u\in V-S}$, the set ${\textstyle S\cup \lbrace u\rbrace }$ is not a ${\textstyle P}$-set while it is a minimal     ${\textstyle P}$-set if no proper subset of ${\textstyle S}$ is a ${\textstyle P}$-set. Clearly, minimal ${\textstyle P}$-sets are 1-minimal ${\textstyle P}$-sets but not the converse; and the converse holds when the property ${\textstyle P}$ is super hereditary. Certainly, the property that isolate domination is neither hereditary nor super-hereditary. But still, for this property as well, the minimality and 1-minimality are equivalent as shown below.

Proposition 3.2.

Let  ${\textstyle S}$be any isolate dominating set of a graph  ${\textstyle G}$. Then  ${\textstyle S}$is minimal if and only if  ${\textstyle S}$is  1-minimal.

Proof.

Let ${\textstyle S}$ be a 1-minimal isolate dominating set of ${\textstyle G}$. Suppose there exists a proper subset ${\textstyle S^{'}}$ of ${\textstyle S}$ that is also an isolate dominating set of ${\textstyle G}$. Then ${\textstyle S^{'}}$ will contain all the isolates of ${\textstyle \left\langle S\right\rangle }$. That is, what remains in ${\textstyle S-S^{'}}$ are non-isolates of ${\textstyle \left\langle S\right\rangle }$. Choose one of those vertices of ${\textstyle S-S^{'}}$, say ${\textstyle v}$. Then the set ${\textstyle S-\lbrace v\rbrace }$ is an isolate dominating set of ${\textstyle G}$, which is a contradiction to the 1-minimality of ${\textstyle S}$. Converse is obvious. □

Theorem 3.3.

An isolate dominating set  ${\textstyle S}$of a graph  ${\textstyle G}$is minimal if and only if every vertex in  ${\textstyle S}$has a private neighbour with respect to  ${\textstyle S}$.

Proof.

Let ${\textstyle S}$ be a minimal isolate dominating set and ${\textstyle u}$ be a vertex of ${\textstyle S}$. If ${\textstyle u}$ is an isolate in ${\textstyle \left\langle S\right\rangle }$ then ${\textstyle u}$ is a private neighbour of itself. Suppose ${\textstyle u}$ is not an isolate of ${\textstyle \left\langle S\right\rangle }$. If ${\textstyle u}$ has no private neighbour with respect to ${\textstyle S}$ then the set ${\textstyle S-\lbrace u\rbrace }$ will be an isolate dominating set. This contradicts the minimality of ${\textstyle S}$ and therefore ${\textstyle u}$ must have a private neighbour with respect to ${\textstyle S}$.

Conversely, suppose ${\textstyle S}$ is an isolate dominating set of ${\textstyle G}$ and every vertex of ${\textstyle S}$ has a private neighbour with respect to ${\textstyle S}$. We now show that ${\textstyle S}$ is a minimal isolate dominating set. If not, then by Proposition 3.2, ${\textstyle S}$ cannot be a 1-minimal dominating set of ${\textstyle G}$ and so there is a vertex ${\textstyle u}$ in ${\textstyle S}$ such that ${\textstyle S-\lbrace u\rbrace }$ is an isolate dominating set of ${\textstyle G}$. Therefore, every vertex in ${\textstyle V-(S-\lbrace u\rbrace )}$ must have at least one neighbour in ${\textstyle S-\lbrace u\rbrace }$ and consequently the vertex ${\textstyle u}$ can have no private neighbours with respect ${\textstyle S}$. This contradicts our assumption and hence the result follows. □

Corollary 3.4.

If  ${\textstyle S\subseteq V(G)}$is an isolate dominating set of  ${\textstyle G}$which is minimal with respect to isolate domination, then  ${\textstyle S}$is a minimal dominating set of  ${\textstyle G}$.

Proof.

Let ${\textstyle S}$ be a minimal isolate dominating set. Then by Theorem 3.3, every vertex of ${\textstyle S}$ has a private neighbour with respect to ${\textstyle S}$ and consequently Theorem 1.1 implies that ${\textstyle S}$ is a minimal dominating set. □

Corollary 3.5.

For any graph  ${\textstyle G}$, we have  ${\textstyle \gamma (G)\leq \gamma _{0}(G)\leq \Gamma _{0}(G)\leq \Gamma (G)}$.

Proposition 3.6.

Every maximal independent set is a minimal isolate dominating set.

Proof.

Let ${\textstyle S}$ be a maximal independent set. Then every vertex in ${\textstyle V-S}$ is adjacent to at least one vertex of ${\textstyle S}$. Therefore ${\textstyle S}$ is a dominating set. As ${\textstyle S}$ is an independent set it is actually an isolate dominating set and also every vertex of ${\textstyle S}$ has a private neighbour with respect to ${\textstyle S}$ namely itself and so the result follows from Theorem 3.3. □

Corollary 3.7.

For any graph  ${\textstyle G}$,  ${\textstyle \gamma _{0}(G)\leq i(G)\leq \beta _{0}(G)\leq \Gamma _{0}(G)}$.

Corollary 3.5 and Corollary 3.7 together establish the required extended domination chain mentioned in Proposition 3.1.

Let us now consider the corona ${\textstyle H=K_{3}\circ mK_{1}}$. It is straight forward to verify that ${\textstyle \gamma (H)=3}$, ${\textstyle \gamma _{0}(H)=m+2}$ and ${\textstyle i(H)=2m+1}$. This gives the following proposition.

Proposition 3.8.

For every positive integer  ${\textstyle r}$there exists a graph  ${\textstyle G}$such that  ${\textstyle i(G)-\gamma _{0}(G)>r}$and  ${\textstyle \gamma _{0}(G)-\gamma (G)>r}$.

Proposition 3.8 says that the differences ${\textstyle i-\gamma _{0}}$ and ${\textstyle \gamma _{0}-\gamma }$ are arbitrary. In fact, the parameters ${\textstyle \gamma ,\gamma _{0}}$ and ${\textstyle i}$ can assume arbitrary values as shown in the following theorem. Further, one can observe that ${\textstyle i(G)=\gamma _{0}(G)}$ when ${\textstyle \gamma _{0}(G)\leq 2}$ and ${\textstyle \gamma _{0}(G)=1}$ if and only if ${\textstyle \gamma (G)=1}$.

Theorem 3.9.

Let  ${\textstyle a}$and  ${\textstyle b}$be two positive integers with  ${\textstyle a\leq b}$. Then there exist graphs  ${\textstyle G}$and  ${\textstyle H}$such that

• ${\textstyle \gamma _{0}(G)=a}$and  ${\textstyle i(G)=b}$, if  ${\textstyle a\geq 3}$.
• ${\textstyle \gamma (H)=a}$and  ${\textstyle \gamma _{0}(H)=b}$, if  ${\textstyle a\geq 2}$.

Proof.

(i) Consider the path ${\textstyle P=(u_{1},u_{2},\ldots ,u_{3a-3})}$ on ${\textstyle 3a-3}$ vertices and attach ${\textstyle b-a+1}$ pendant vertices at each of ${\textstyle u_{1}}$ and ${\textstyle u_{2}}$. Now, let ${\textstyle G}$ be the resultant graph. Certainly, the set ${\textstyle \lbrace u_{1},u_{2}\rbrace \cup \lbrace u_{5+3i}/i\in \lbrace 0,1,2,3,\ldots ,a-3\rbrace \rbrace }$ is an isolate dominating set of ${\textstyle G}$ with cardinality ${\textstyle a}$ and so ${\textstyle \gamma _{0}(G)\leq a}$. Since ${\textstyle G-(N[u_{1}]\cup N[u_{2}])}$ is a path, ${\textstyle \gamma (G-(N[u_{1}]\cup N[u_{2}]))=\lceil {\frac {3a-6}{3}}\rceil =a-2}$. Also at least two vertices are required to dominate the set ${\textstyle N[u_{1}]\cup N[u_{2}]}$ and so ${\textstyle \gamma _{0}(G)\geq a}$. Hence ${\textstyle \gamma _{0}(G)=a}$. Now, the set ${\textstyle \lbrace u_{2}\rbrace \cup \lbrace u_{5+3i}/i\in \lbrace 0,1,2,3,\ldots ,a-3\rbrace \rbrace }$ together with the pendant vertices adjacent to ${\textstyle u_{1}}$ is an independent dominating set of ${\textstyle G}$ with cardinality ${\textstyle b}$ and therefore ${\textstyle i(G)\leq b}$. Further, if ${\textstyle I}$ is an independent dominating set of ${\textstyle G}$, then both ${\textstyle u_{1}}$ and ${\textstyle u_{2}}$ cannot be in ${\textstyle I}$ simultaneously. If ${\textstyle u_{1}\in I}$, then ${\textstyle I}$ must contain all the ${\textstyle b-a+1}$ pendant vertices adjacent to ${\textstyle u_{2}}$ and similar argument follows when ${\textstyle I}$ contains ${\textstyle u_{2}}$. Also as discussed above a dominating set of ${\textstyle G-(N[u_{1}]\cup N[u_{2}])}$ requires at least ${\textstyle a-2}$ vertices and hence ${\textstyle i(G)\geq 1+b-a+1+a-2=b}$. Thus ${\textstyle i(G)=b}$.

(ii) Let ${\textstyle H}$ be the graph consisting of a path on ${\textstyle a}$ vertices and ${\textstyle b-a+1}$ pendant edges attached with each vertex of the path. Now it can be easily verified that ${\textstyle \gamma _{0}(H)=b}$ and ${\textstyle \gamma (H)=a}$. □

4. Bounds

In this section we obtain some bounds for the isolate domination number ${\textstyle \gamma _{0}}$. Obviously the value of ${\textstyle \gamma _{0}}$ for a graph of order ${\textstyle n}$ ranges from 1 to ${\textstyle n}$. The earlier is attained only for graphs with maximum degree ${\textstyle n-1}$ and the later is attained only for graphs with no edges. Further, it has been proved in  [1] that ${\textstyle \gamma _{0}(G)=n-1}$ if and only if ${\textstyle G=P_{2}}$. The following proposition characterizes the connected graphs ${\textstyle G}$ of order ${\textstyle n}$ for which ${\textstyle \gamma _{0}(G)=n-2}$.

Proposition 4.1.

Let  ${\textstyle G}$be a connected graph of order  ${\textstyle n}$. Then  ${\textstyle \gamma _{0}(G)=n-2}$if and only if  ${\textstyle G}$is one of the graphs  ${\textstyle P_{3}}$,  ${\textstyle P_{4}}$,  ${\textstyle C_{3}}$and  ${\textstyle C_{4}}$.

Proof.

Suppose ${\textstyle \gamma _{0}(G)=n-2}$ and ${\textstyle S}$ is a ${\textstyle \gamma _{0}}$-set. Then ${\textstyle \left\langle V-S\right\rangle =K_{2}}$ or ${\textstyle {\overline {K_{2}}}}$. It is enough to prove that ${\textstyle n\leq 4}$. By Theorem 1.3, ${\textstyle V-S}$ is a dominating set of ${\textstyle G}$. Now, if ${\textstyle \left\langle V-S\right\rangle ={\overline {K_{2}}}}$, then ${\textstyle V-S}$ will be an isolate dominating set of ${\textstyle G}$ and hence ${\textstyle n\leq 4}$. Suppose ${\textstyle \left\langle V-S\right\rangle =K_{2}}$. If a vertex ${\textstyle u}$ in ${\textstyle V-S}$ has more than one neighbour in ${\textstyle S}$, then ${\textstyle (S-N(u))\cup \lbrace u\rbrace }$ will be an isolate dominating set of ${\textstyle G}$ with cardinality less than ${\textstyle n-2}$, giving a contradiction. Therefore each of the two vertices in ${\textstyle V-S}$ has at most one neighbour in ${\textstyle S}$, which implies that ${\textstyle \vert S\vert \leq 2}$ and consequently we have ${\textstyle n\leq 4}$. Converse is obvious. □

In view of Theorem 1.3, the value of the domination number ${\textstyle \gamma (G)}$ of a graph ${\textstyle G}$ will not exceed half of the order of ${\textstyle G}$. But unlike dominating sets, the complement of a minimal isolate dominating set need not be an isolate dominating set. For instance, in a double star the set of all pendant vertices is a minimal isolate dominating set whereas its complement is not an isolate dominating set. However, the isolate domination number ${\textstyle \gamma _{0}}$ does not exceed ${\textstyle {\frac {n}{2}}}$, where ${\textstyle n}$ is the order of the given graph. This is proved in the following theorem.

Theorem 4.2.

If  ${\textstyle G}$is a connected graph on  ${\textstyle n}$vertices, then  ${\textstyle \gamma _{0}(G)\leq {\frac {n}{2}}}$. Further, if  ${\textstyle a}$and  ${\textstyle b}$are positive integers with  ${\textstyle b\geq 2a}$then there exists a graph  ${\textstyle G}$on  ${\textstyle b}$vertices such that  ${\textstyle \gamma _{0}(G)=a}$.

Proof.

Let ${\textstyle D}$ be a ${\textstyle \gamma }$-set of ${\textstyle G}$. If ${\textstyle \left\langle D\right\rangle }$ has an isolate then ${\textstyle D}$ itself is a minimal isolate dominating set and so we are through. Suppose ${\textstyle \left\langle D\right\rangle }$ has no isolates. Then it follows from Theorem 1.1 that every vertex in ${\textstyle D}$ has a private neighbour in ${\textstyle V-D}$ with respect to ${\textstyle D}$. Let ${\textstyle u}$ be a vertex in ${\textstyle D}$ having minimum number of private neighbours, say ${\textstyle k}$, with respect to ${\textstyle D}$ and therefore ${\textstyle \gamma +\gamma k\leq n}$. Also, it is clear that the set ${\textstyle X=(D-\lbrace u\rbrace )\cup S}$, where ${\textstyle S}$ is a ${\textstyle \gamma _{0}}$-set of ${\textstyle \left\langle pn[u,D]\right\rangle }$, is an isolate dominating set of ${\textstyle G}$ so that ${\textstyle \gamma _{0}(G)\leq \vert X\vert \leq \gamma -1+k}$. We now claim that ${\textstyle \gamma -1+k\leq {\frac {\gamma +\gamma k}{2}}}$. Obviously, this inequality is true when ${\textstyle \gamma =2}$. Now if ${\textstyle 2(\gamma -1+k)>\gamma +\gamma k}$, where ${\textstyle \gamma \not =2}$, then ${\textstyle (\gamma -2)>k(\gamma -2)}$ and thus getting a contradiction, as ${\textstyle k>1}$. Hence ${\textstyle \gamma _{0}(G)\leq \vert X\vert \leq \gamma -1+k\leq {\frac {\gamma +\gamma k}{2}}\leq {\frac {n}{2}}}$.

Now, suppose ${\textstyle a}$ and ${\textstyle b}$ are any two positive integers with ${\textstyle b\geq 2a}$. Let ${\textstyle H}$ be any connected graph on ${\textstyle a}$ vertices. Then, for the graph ${\textstyle G}$ obtained by attaching ${\textstyle b-2a+1}$ pendant vertices at exactly one vertex of ${\textstyle H}$ and attaching exactly one pendant vertex at each of the remaining vertices, we have ${\textstyle \gamma _{0}(G)=a}$ and ${\textstyle \vert V(G)\vert =b}$. □

Remark 4.3.

It is quite obvious that for any vertex ${\textstyle v}$ of a graph ${\textstyle G}$ the set ${\textstyle S=V(G)-N(v)}$ is an isolate dominating set of ${\textstyle G}$. As this is true in particular for a vertex of maximum degree, it follows that ${\textstyle \gamma _{0}(G)\leq n-\Delta (G)}$. Clearly, this bound is attained for all graphs with ${\textstyle \Delta (G)=n-1}$ and also for the complete bipartite graphs.

The reader may be quite familiar with the result that for a graph ${\textstyle G}$ of diameter two, ${\textstyle \gamma (G)\leq \delta (G)}$. But it is not true in the case of isolate domination number. For example, the graph ${\textstyle G}$ of Fig. 1 is of diameter two whereas ${\textstyle \gamma _{0}(G)=3}$ that exceeds ${\textstyle \delta (G)}$.

Fig. 1. A graph ${\textstyle G}$ of diameter two with ${\textstyle \gamma _{0}(G)>\delta (G)}$.

Proposition 4.4.

If  ${\textstyle G}$is a triangle free graph without isolated vertices, then  ${\textstyle \gamma _{0}({\overline {G}})=2}$.

Proof.

As ${\textstyle G}$ has no isolated vertices, there exists at least one edge ${\textstyle xy}$ in ${\textstyle G}$. As ${\textstyle G}$ is triangle-free, no vertex in ${\textstyle G}$ is adjacent to both ${\textstyle x}$ and ${\textstyle y}$ and therefore the set ${\textstyle \lbrace x,y\rbrace }$ will form an isolate dominating set in ${\textstyle {\overline {G}}}$ and so ${\textstyle \gamma _{0}({\overline {G}})\leq 2}$. If ${\textstyle \gamma _{0}({\overline {G}})=1}$, then ${\textstyle G}$ has an isolated vertex, a contradiction to the assumption that ${\textstyle G}$ has no isolated vertices. □

Proposition 4.5.

For any graph  ${\textstyle G}$on  ${\textstyle n}$vertices,  ${\textstyle \gamma _{0}(G)+\alpha _{0}(G)\leq n}$, where  ${\textstyle \alpha _{0}(G)}$is the vertex covering number of  ${\textstyle G}$. This bound is sharp.

Proof.

Let ${\textstyle S}$ be a vertex cover of ${\textstyle G}$ with ${\textstyle \vert S\vert =\alpha _{0}(G)}$. If a vertex ${\textstyle u\in S}$ is not dominated by any vertex of ${\textstyle V-S}$, then ${\textstyle S-\lbrace u\rbrace }$ will be a vertex cover of cardinality less than ${\textstyle \alpha _{0}}$ and therefore ${\textstyle V-S}$ is a dominating set of ${\textstyle G}$. Further, as ${\textstyle S}$ is a vertex cover of ${\textstyle G}$, ${\textstyle V-S}$ is an independent set. Thus, ${\textstyle V-S}$ is an isolate dominating set of ${\textstyle G}$ and hence ${\textstyle \gamma _{0}(G)\leq \vert V-S\vert =n-\alpha _{0}(G)}$.

This bound is attained for the graph ${\textstyle G}$ of Fig. 2 as ${\textstyle \gamma _{0}(G)=2}$, ${\textstyle \alpha _{0}(G)=3}$ and ${\textstyle n=5}$. □

Next we obtain a bound along with the characterization for the upper isolate domination number ${\textstyle \Gamma _{0}}$. It is obvious that for any graph ${\textstyle G}$, ${\textstyle 1\leq \Gamma _{0}(G)\leq n}$ and ${\textstyle \Gamma _{0}(G)=n}$ if and only if ${\textstyle G}$ is a graph with no edges. Further, as ${\textstyle \beta _{0}(G)\leq \Gamma _{0}(G)}$, it follows that ${\textstyle \Gamma _{0}(G)=1}$ if and only if ${\textstyle G}$ is ${\textstyle K_{n}}$. Moreover, as ${\textstyle \Gamma _{0}(G)\leq \Gamma (G)}$, it follows from Theorem 1.2 that ${\textstyle \Gamma _{0}(G)\leq n-\delta }$. The following theorem characterizes the graphs whose upper isolate domination number is ${\textstyle n-\delta }$.

Theorem 4.6.

For any graph  ${\textstyle G}$of order  ${\textstyle n}$, the following are equivalent.

• ${\textstyle \Gamma (G)=n-\delta (G)}$.
• ${\textstyle \Gamma _{0}(G)=n-\delta (G)}$.
• ${\textstyle G={\overline {K_{n-\delta (G)}}}+H}$, where  ${\textstyle H}$is any graph of order  ${\textstyle \delta (G)}$.

Proof.

${\textstyle (i)\Leftrightarrow (ii)}$

Assume that ${\textstyle \Gamma (G)=n-\delta (G)}$ and let ${\textstyle S}$ be a ${\textstyle \Gamma }$-set of ${\textstyle G}$. As ${\textstyle S}$ is a minimal dominating set, by Theorem 1.1, every vertex of ${\textstyle S}$ must have at least one private neighbour with respect to ${\textstyle S}$. Consider a vertex ${\textstyle u\in S}$ and a minimal isolate dominating set ${\textstyle S_{1}}$ of ${\textstyle \left\langle pn[u,S]\right\rangle }$. Clearly, the set ${\textstyle D=(S-\lbrace u\rbrace )\cup S_{1}}$ is an isolate dominating set of ${\textstyle G}$. Also, every vertex of ${\textstyle D}$ has a private neighbour with respect to ${\textstyle D}$. Therefore Theorem 3.3 implies that ${\textstyle D}$ is a minimal isolate dominating set of ${\textstyle G}$ so that ${\textstyle \Gamma _{0}(G)\geq \vert D\vert =\vert S\vert -1+\vert S_{1}\vert \geq n-\delta (G)}$ as ${\textstyle \vert S\vert =n-\delta (G)}$ and ${\textstyle \vert S_{1}\vert \geq 1}$. As ${\textstyle \Gamma _{0}(G)\leq \Gamma (G)}$ it follows that ${\textstyle \Gamma _{0}(G)\leq n-\delta (G)}$. Thus ${\textstyle \Gamma _{0}(G)=n-\delta (G)}$. Conversely, if ${\textstyle \Gamma _{0}(G)=n-\delta (G)}$, then ${\textstyle n-\delta \leq \Gamma (G)}$ as ${\textstyle \Gamma _{0}(G)\leq \Gamma (G)}$ and therefore it follows from Theorem 1.2 that ${\textstyle \Gamma (G)=n-\delta (G)}$.

${\textstyle (ii)\Leftrightarrow (iii)}$

Assume that ${\textstyle \Gamma _{0}(G)=n-\delta (G)}$ and let ${\textstyle S}$ be a ${\textstyle \Gamma _{0}}$-set of ${\textstyle G}$ of cardinality ${\textstyle n-\delta }$ and ${\textstyle u}$ be an isolated vertex in ${\textstyle \left\langle S\right\rangle }$. Then ${\textstyle u}$ is adjacent to all the vertices of ${\textstyle V-S}$. Hence no vertex of ${\textstyle V-S}$ can be a private neighbour of any vertex of ${\textstyle S}$ other than the vertex ${\textstyle u}$. Hence Theorem 3.3 implies that every vertex of ${\textstyle S-\lbrace u\rbrace }$ is a private neighbour of itself so that ${\textstyle S}$ is an independent set of ${\textstyle G}$ and consequently every vertex of ${\textstyle S}$ is adjacent to all the vertices of ${\textstyle V-S}$. Then ${\textstyle G={\overline {K_{n-\delta (G)}}}+H}$, where ${\textstyle H}$ is a graph of order ${\textstyle \delta (G)}$.

Conversely, suppose ${\textstyle G={\overline {K_{n-\delta (G)}}}+H}$, where ${\textstyle H}$ is a graph of order ${\textstyle \delta (G)}$. Then the set ${\textstyle V({\overline {K_{n-\delta (G)}}})}$ is a minimal isolate dominating set of ${\textstyle G}$ so that ${\textstyle \Gamma _{0}(G)\geq n-\delta (G)}$. The other inequality follows immediately from Theorem 1.2 and the extended domination chain given in Proposition 3.1. □

5. Cubic graphs

Here we discuss the isolate domination parameters for cubic graphs.

Proposition 5.1.

If  ${\textstyle G}$is an  ${\textstyle r}$-regular graph with  ${\textstyle r\geq 2}$, then  ${\textstyle \gamma _{0}(G)\leq \gamma (G)+r-2}$and the bound is sharp.

Proof.

Let ${\textstyle S}$ be a ${\textstyle \gamma }$-set of ${\textstyle G}$. If ${\textstyle \left\langle S\right\rangle }$ has an isolate then ${\textstyle \gamma _{0}(G)=\gamma (G)}$ and therefore ${\textstyle \gamma _{0}(G)\leq \gamma (G)+r-2}$ as ${\textstyle r\geq 2}$. Now, let us assume that ${\textstyle \left\langle S\right\rangle }$ has no isolates and let ${\textstyle u}$ be a vertex of ${\textstyle S}$. Then ${\textstyle u}$ must have at least one neighbour in ${\textstyle S}$ and so it can have at most ${\textstyle r-1}$ private neighbours with respect to ${\textstyle S}$. Now the set ${\textstyle (S-\lbrace u\rbrace )}$ together with a ${\textstyle \gamma _{0}}$-set of ${\textstyle \left\langle pn[u,S]\right\rangle }$ will form an isolate dominating set of ${\textstyle G}$ and therefore ${\textstyle \gamma _{0}(G)\leq \vert (S-\lbrace u\rbrace )\cup pn[u,S]\vert \leq \gamma +r-2}$. The bound is attained for the complete bipartite graph ${\textstyle K_{r,r}}$. □

Corollary 5.2.

For a cubic graph  ${\textstyle G}$, the value of  ${\textstyle \gamma _{0}(G)}$is either  ${\textstyle \gamma (G)}$or  ${\textstyle \gamma (G)+1}$.

By virtue of Corollary 5.2, the family of all cubic graphs can be split into two classes, namely Class 1 and Class 2 such that cubic graphs for which ${\textstyle \gamma _{0}=\gamma }$ are of Class 1 and the rest are of Class 2. As the value of the parameters ${\textstyle \gamma _{0}}$ and ${\textstyle \gamma }$ are equal to 3 for the Petersen graph, the Class 1 family is non-empty and indeed Class 2 also is non-empty as it includes the complete bipartite graph ${\textstyle K_{3,3}}$.

Lemma 5.3.

Let  ${\textstyle G}$be a  3-regular graph. If  ${\textstyle \gamma _{0}(G)=\gamma (G)+1}$, then for every vertex  ${\textstyle v}$in a  ${\textstyle \gamma }$-set  ${\textstyle D}$of  ${\textstyle G}$,  ${\textstyle pn[v,D]}$is an independent set of cardinality  2.

Proof.

Assume that ${\textstyle \gamma _{0}(G)=\gamma (G)+1}$. Let ${\textstyle D}$ be a ${\textstyle \gamma }$-set of ${\textstyle G}$ and let ${\textstyle v}$ be a vertex in ${\textstyle D}$. Since ${\textstyle \gamma _{0}(G)>\gamma (G)}$, ${\textstyle v}$ is not an isolated vertex of ${\textstyle \left\langle D\right\rangle }$. Therefore, ${\textstyle pn[v,D]}$ is a subset of ${\textstyle V(G)-D}$ with ${\textstyle \vert pn[v,D]\vert \in \lbrace 1,2\rbrace }$. Now, if ${\textstyle \vert pn[v,D]\vert =1}$, then the set ${\textstyle D-\lbrace v\rbrace }$ together with the only private neighbour of ${\textstyle v}$ will form an isolate dominating set of ${\textstyle G}$ with cardinality ${\textstyle \gamma (G)}$ which is a contradiction. Therefore ${\textstyle \vert pn[v,D]\vert =2}$. Further, if ${\textstyle v_{1},v_{2}\in pn[v,D]}$ and ${\textstyle v_{1}v_{2}\in E(G)}$ then ${\textstyle (D-\lbrace v\rbrace )\cup \lbrace v_{1}\rbrace }$ is an isolate dominating set of ${\textstyle G}$ of cardinality ${\textstyle \gamma (G)}$. Hence, ${\textstyle pn[v,D]}$ is an independent set of cardinality two. □

Lemma 5.4.

Let  ${\textstyle G}$be a  3-regular graph. Then  ${\textstyle \gamma _{0}(G)=\gamma (G)+1}$if and only if  ${\textstyle \left\langle D\right\rangle =\cup K_{2}}$, for every  ${\textstyle \gamma }$-set  ${\textstyle D}$of  ${\textstyle G}$.

Proof.

Assume that ${\textstyle \gamma _{0}(G)=\gamma (G)+1}$. Let ${\textstyle D}$ be a ${\textstyle \gamma }$-set of ${\textstyle G}$ and let ${\textstyle v\in D}$. Since ${\textstyle \gamma _{0}(G)>\gamma (G)}$, ${\textstyle v}$ is not an isolated vertex of ${\textstyle \left\langle D\right\rangle }$. By Theorem 1.1, the vertex ${\textstyle v}$ has a private neighbour in ${\textstyle V-D}$. Therefore ${\textstyle v}$ can have at most two neighbours in ${\textstyle D}$. If ${\textstyle v}$ has two neighbours in ${\textstyle D}$ then the set ${\textstyle D-\lbrace v\rbrace }$ together with the only private neighbour of ${\textstyle v}$ will form a ${\textstyle \gamma _{0}}$-set of ${\textstyle G}$ of cardinality ${\textstyle \gamma (G)}$. Hence ${\textstyle v}$ has exactly one neighbour in ${\textstyle D}$.

Conversely, let ${\textstyle \left\langle D\right\rangle =\cup K_{2}}$, for every minimum dominating set ${\textstyle D}$ of ${\textstyle G}$. Now, we have to prove that ${\textstyle \gamma _{0}(G)=\gamma (G)+1}$. In contrary, if ${\textstyle \gamma _{0}(G)=\gamma (G)}$ then the corresponding ${\textstyle \gamma _{0}}$-set is a minimum dominating set of ${\textstyle G}$ having an isolated vertex. This contradicts our assumption. □

6. Open problems

This paper introduces a new variation of domination namely isolate domination and just initiates a study on this notion. We list some interesting problems for further research that we encountered during the course of our investigation.

• Find a characterization of graphs ${\textstyle G}$ for which ${\textstyle (i)}$${\textstyle \gamma (G)=\gamma _{0}(G)}$${\textstyle (ii)}$${\textstyle \gamma _{0}(G)={\frac {n}{2}}}$ and ${\textstyle (iii)}$${\textstyle \gamma _{0}(G)=i(G)}$.
• Find a structural characterization of cubic graphs ${\textstyle G}$ for which ${\textstyle \gamma _{0}(G)=\gamma (G)+1}$.
• Obtain good bounds for both ${\textstyle \gamma _{0}(G)}$ and ${\textstyle \Gamma _{0}(G)}$.
• Study of these parameters for trees would be interesting.

Acknowledgment

Research of the first author is supported by DST-SERB Project SR/FTP/MS-002/2012.

References

1. [1] Benjier H. Arriola; Isolate domination in the join and corona of graphs; Appl. Math. Sci., 9 (2015), pp. 1543–1549
2. [2] G. Chartrand, Lesniak; Graphs and Digraphs; (fourth ed.)CRC press, Boca Raton (2005)
3. [3] E.J. Cockayne, S.T. Hedetniemi, K.J. Miller; Properties of hereditary hypergraphs and middle graphs; Canad. Math. Bull., 21 (1978), pp. 461–468
4. [4] G.S. Domke, Jean E. Dunbar, Lisa R. Markus; Gallai-type theorems and domination parameters; Discrete Math. (1997), pp. 237–248
5. [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater; Domination in Graphs: Advanced Topics; Marcel Dekker, New York (1998)
6. [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater; Fundamentals of domination in Graphs; Marcel Dekker, New York (1998)
7. [7] S.T. Hedetneimi, R. Laskar (Eds.), Discrete Math., 86 (1990)