1. Introduction
The graphs considered here are finite, connected, undirected without loops or multiple edges and without isolated vertices. As usual \(n\) and \(q\) denote the number of vertices and edges of a graph \(G\). For any undefined term or notation in this paper can be found in Harary [
1].
A set \(D \subseteq V\) is a dominating set of \(G\) if every vertex in \(V-D\) is adjacent to some vertex in \(D\). The dominating number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set \(D\). A secure dominating set of \(G\) is a dominating set \(D \subseteq V(G)\) with the property that for each \(u \in V(G)-D\), there exists \( v \in D\) adjacent to \(u\) such that \((D-\lbrace v \rbrace)-\lbrace u \rbrace\) is a dominating set.
The total domination of lict graph has been studied by [
2]. The lict graph \(\eta(G)\) of a graph \(G\) is the graph whose vertex set is the union of the set of edges and the set of cut-vertices of \(G\) in which two vertices are adjacent if and only if the corresponding edges are adjacent or the corresponding members of \(G\) are incident. The secure domination has been intensively studied by [
3,
4]. The secure lict dominating set of a graph \(\eta(G)\) , is a dominating set \(F \subseteq V(\eta(G))\) with the property that for each \(v_{1} \in (V(\eta(G))-F)\), there exists \(v_{2} \in F\) adjacent to \(v_{1}\) such that \((F-\lbrace v_{2}\rbrace) \cup \lbrace v_{1} \rbrace\) is a dominating set of \(\eta(G)\). The secure lict dominating number \(\gamma_{se}(\eta(G))\) of \(G\) is a minimum cardinality of secure lict dominating set of graph \(G\). For complete review on the topic of domination[
5].
The vertex independence number \(\beta_{0}(G)\) is the maximum cardinality among the independent set of vertices of \(G\). \(L(G)\) is the line graph of \(G\), \(\gamma_{e}(G)\) is edge domination number, \(\gamma_{s}^{‘}(G)\) is the secure edge dominating number, \(\gamma_{t}(G)\) is the total dominating number , \(\gamma_{ns}(G)\) is the non-split dominating number and \(\chi(G)\)is the chromatic number of \(G\). The degree of a edge [
6] is the number of lines adjacent to it. The minimum (maximum) degree of an edge in \(G\) is denoted by \(\delta^{‘}(\Delta^{‘})\). A subdivision of an edge \(e=uv\) of a graph \(G\) is the replacement of an edge \(e\) by a path \((u,v,w)\) where \(w \notin E(G)\). The graph obtained from \(G\) by subdividing each edge of \(G\) exactly once is called the subdivision graph of \(G\) and is denoted by \(S(G)\). For any real number \(X\),\(\lceil X \rceil\) denotes the smallest integer not less than \(X\) and \(\lfloor X \rfloor\) denotes the greatest integer not greater than \(X\).
In this paper we established the relationship of this concept with the other domination parameters is investigated.
2. Main results
Theorem 2.1.
First we list out the exact values of \(\gamma_{se}(\eta(G))\) for some standard graphs:
- (i) For any cycle \(C_{n}\) with \(n \geq 3\) vertices,
\[ \gamma_{se}(\eta(C_{n})) = \left\{
\begin{array}{l l}
1 & \quad \text{ \(n=3\). }
\lfloor\frac{n+1}{2}\rfloor & \quad \text{ n \(\ncong\) 0(mod 7).}
(\frac{3n}{7}) & \quad \text{ n \(\cong\) 0(mod 7).}
\end{array} \right.\]
- (ii) For any path \(P_{n}\) with \(n \geq 4\) vertices,\(\gamma_{se}(\eta(P_{n}))=n-2\).
- (iii) For any star graph \(K_{1,n}\) with \(n \geq 2\) vertices, \(\gamma_{se}(\eta(K_{1,n}))=1\).
- (iv) For any wheel graph \(W_{n}\) with \(n \geq 4\) vertices, \(\gamma_{se}(\eta(W_{n}))=\lceil\frac{3n}{7}\rceil+1\).
- (v) For any bipartite graph \(K_{m,n}\) with \(m,n \geq 2\) vertices, \(\gamma_{se}(\eta(K_{m,n}))=min\lbrace m,n \rbrace\).
- (vi) For any friendship graph \(F_{n}\) with \(k\) blocks, \(\gamma_{se}(\eta(F_{n}))=k\).
- (vii) For any complete graph \(K_{n},n \geq 4\), \(\gamma_{se}(\eta(K_{n}))= \lceil \frac{n}{2}\rceil\).
Theorem 2.2.
Let \(G\) be the connected graph with \(n \geq 3\) vertices, then \(\gamma_{se}(\eta(G))=1\) if and only if \(G=K_{1,n-1}\) or \(C_{3}\).
Proof.
Necessary: Suppose \(\gamma_{se}(\eta(G))=1\). We consider the following cases:
- Case 1: If \(G\) is a connected graph with \(n=3\), then \(G\) is either \(K_{1,2}\) or \(C_{3}\), by using Theorem 2.1(i) and Theorem 2.1(iii), \(\gamma_{se}(\eta(G))=1\).
- Case 2: If \(G\) is a connected graph with \(n \geq 4\). Let \(D=\lbrace e \rbrace\) be the secure dominating set of \(\gamma_{se}(\eta(G))\). To prove that \(G=K_{1,n-1}\), we assume contrary that \(G \neq K_{1,n-1}\). We consider the following subcases:
- Subcase 1:
Let \(F=K_{1,n-1}\) and let the endvertices \(v_{1},v_{2} \in V(F)\), such that the graph \(G\) is obtained form \(F\) by adding the edge \(e_{1}=(v_{1},v_{2}) \notin E(F)\). It follows that the set \((D-\lbrace e\rbrace) \cup \lbrace e_{1} \rbrace\) is not a dominating set of \(\eta(G)\). This implies that \(D\) is not a dominating set of \(\eta(G)\), which is a contradiction. Thus \(G=K_{1,n-1}\).
- Subcase 2:
Let \(F=K_{1,n-1}\) and an endvertex \(v_{1}\in V(F)\), such that the graph \(G\) is obtained form \(F\) by adding the vertex \(v \in V(F)\)and the edge \(e_{1}=(v,v_{1})\). It follows that the set \((D-\lbrace e\rbrace) \cup \lbrace e_{1} \rbrace\) is not an secure dominating set of \(\eta(G)\). This implies that \(D\) is not a dominating set of \(\eta(G)\), which is a contradiction. Thus \(G=K_{1,n-1}\).
Sufficiency:
If \(G=K_{1,n-1}\) or \(G=C_{3}\), then using Theorem 2.1(i)and Theorem 2.1(iii),\(\gamma_{se}(\eta(G))=1\).
Theorem 2.3.
For any graph \(G\), \(\gamma_{se}(\eta(G))\geq\gamma_{s}^{‘}(G)\). Equality holds if \(G\) is non-separable.
Proof.
Let \(D\) be a secure edge dominating set of \(G\) and let \(B\) be the corresponding vertices of \(D\) in \(\eta(G)\). We consider the following cases:
- Case 1:
Suppose the cut-vertices of \(G\) are incident with atleast one edge of \(D\) in \(G\).
Then for each cut-vertex say \(v_{i}\) in \(G\) if there exists an vertex \(v \in B,v \in N(v_{i})\) in \(\eta(G)\) such that \((B-\lbrace v\rbrace) \cup \lbrace v_{i} \rbrace\) is the dominating set of \(\eta(G)\). Then \(\gamma_{se}(\eta(G))=\gamma_{s}^{‘}(G)\).
Otherwise \(B \cup \lbrace v_{i}\rbrace\) is the secure dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\geq\gamma_{s}^{‘}(G)\).
- Case 2:
Suppose if there exists atleast one cut-vertex \(v_{i}\) in \(G\) which is not incident with any edge of \(D\), then \(B \cup \lbrace v_{i}\rbrace\) is the secure dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\geq\gamma_{s}^{‘}(G)\).
To prove the equality:
If \(G\) is non-separable, then \(\eta(G)=L(G)\). Hence \(\gamma_{se}(\eta(G))=\gamma_{se}(L(G))=\gamma_{s}^{‘}(G)\).
Theorem 2.4.
For any graph \(G\), \(\gamma_{se}(\eta(G))\geq\gamma_{e}(G)\).
Proof.
Let \(D\) be a \(\gamma_{e}\) set of graph \(G\). If \(D\) is a secure dominating set of graph \(\eta(G)\), then
- (i)
For each \(e_{i} \in E(G)-D\), if there exists an edge \(e_{1} \in D\), \(e_{1} \in N(e_{i})\), such that the corresponding vertices of \(\lbrace(D-e_{1}) \cup e_{i} \rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\).
- (ii)
For each cut-vertex \(c_{i}\in G\), if there exists an edge \(e_{i} \in D\), \(c_{i}\) is incident with \(e_{i}\) in \(G\) such that the corresponding vertices of \(\lbrace (D- \lbrace e_{i} \rbrace) \cup c_{i}\rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\).
Therefore \(\gamma_{se}(\eta(G))=\gamma_{e}(G)\). Otherwise the corresponding vertices of \(\lbrace D\cup e_{i} \cup c_{i} \rbrace\) in \(\eta(G)\) is the secure dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\geq\gamma_{e}(G)\).
Theorem 2.5.
For any Tree \(T\), \(\gamma_{se}(\eta(T)) \leq m\), where \(‘m’\) is the number of cut-vertices of \(T\). Equality will holds for \(P_{n}\) and \(K_{1,n}\).
Proof.
Let \(A\) be the set of cut-vertices of a graph \(T\) with \(\vert A \vert=m\). Since \(A\) covers all the edges of \(T\), therefore in \(\eta(T)\), \(A\) covers all the vertices of \(\eta(T)\). Hence the set \(A\) is the lict dominating set of \(T\). Now for each vertex \(e_{i}\in V(\eta(T))-A\), there exists a vertex \( \lbrace c_{i} \rbrace \in A\) incident with \(\lbrace e_{i} \rbrace\) in \(T\) such that \((A-\lbrace c_{i} \rbrace) \cup \lbrace e_{i} \rbrace\) is a lict dominating set of \(T\). Therefore \(\gamma_{se}(\eta(T)) \leq m\).
For Equality:
The result follows from Theorem 2.1(ii) and Theorem 2.1(iii).
Theorem 2.6.
For any Tree \(T\) , \(\gamma_{se}(\eta(T))+1 \geq \chi(T)\).
Proof.
We have \(\chi (T)=2\) and \(\gamma_{se}(T)+1 \geq 2\), the result follows.
Theorem 2.7.
If every vertex of \(G\) is adjacent to an end vertex then, \(\gamma_{se}(\eta(G))=m\), where \(m\) is the number of cut-vertices of \)G\(.
Proof.
Let \(A\) be the set of cut-vertices of \(G\) with \(\vert A \vert=m\) and let \(B=\lbrace e_{i}/e_{i}\) is incident with \((v_{i},v_{j}),v_{i} \in A,d(v_{j})=1\rbrace\) with \(\vert B\vert=m\). Suppose \(\gamma_{se}(\eta(G)) < m\), then \(A\) is not the dominating set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G)) \geq m\). Now if \(\gamma_{se}(\eta(G))=\vert A\vert\), then for each edge \(e_{i} \in E(G)-B\), there exists an edge \(e_{j} \in N(e_{i}) \cap B \) such that the corresponding vertices of \(\lbrace(B-e_{j})\cup e_{i}\rbrace\) is the dominating set of \(\eta(G)\) and for every cut-vertex \(v_{i} \in A\), there exists an edge \(e_{i} \in B\) incident with \(v_{i}\) such that the corresponding vertices of \(\lbrace (A-e_{j})\cup v_{i}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G))=m\).
Corollary 2.8.
If every vertex of \(G\) is adjacent to an end vertex, then \(\gamma_{se}(\eta(G))=\gamma(G)=\gamma_{t}(G)=\gamma_{ns}(G)\).
Proof.
Since every vertex of \(G\) is adjacent to an end vertex then, \(\gamma(G)=\gamma_{t}(G)=\gamma_{ns}(G)=m\) and by using Theorem 2.7, the result follows.
Theorem 2.9.
For any connected graph \(G\), \(\gamma_{se}(\eta(G)) \leq q-\Delta^{‘}(G)+1\), \( q \geq 2\) and \(\Delta^{‘}\) is the maximum degree of an edge.
Proof.
Let \(e\) be an edge with degree \(\Delta^{‘}\) and let \(S\) be the set of edges adjacent to \(e\) in \(G\). Then \(E(G)-S\) is the lict dominating set of \(G\). We consider the following cases:
- Case 1:
If \(G\) is a non-separable graph, then for every edge \(e_{1} \in S\), there exist an edge \(e_{2} \in E(G)-S\), \(e_{1} \in N(e_{2})\) such that the corresponding vertices of \(\lbrace(E(G)-S)-e_{2}\rbrace \cup \lbrace e_{1} \rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G)) \leq q-\Delta^{‘}(G)\).
- Case 2:
If \(G\) is a separable graph. We consider the following subcases:
- (i)
If \(((E(G)-S) \cup e)\) is a null graph in \(G\), then \(\Delta^{‘}(G)=q-1\) and in the graph \(G\), \(e=v_{1}v_{2}\), where \(v_{1}\) or \(v_{2}\) or both, are the cut-vertices of graph \(G\). Therefore by using Theorem \(2.7\) , \(\gamma_{se}(\eta(G))=\vert \lbrace v_{1} \cup v_{2})\rbrace\vert\) or \(\vert \lbrace v_{1} \rbrace \vert\) or \(\vert \lbrace v_{2} \rbrace\vert = 2\) or \(1\). Therefore \(\gamma_{se}(\eta(G)) \leq q-\Delta^{‘}(G)+1\).
- (ii)
If \(((E(G)-S)\cup e)\) is not a null graph and \(e_{1}=(v_{1},v_{2})\) where \(v_{1},v_{2}\) are the cut-vertices of the graph \(G\). Now if \(v_{1} \notin \gamma_{se}\) set of \(\eta(G)\), then \(v_{2}\) is not covered by any vertex corresponding to the vertices of \(E(G)-S\) in \(\eta(G)\). Therefore the corresponding vertices of \((E(G)-S)\cup \lbrace v_{1} \rbrace\) in \(\eta(G)\) is the secure dominating set of \(\eta(G)\). Therefore \(\gamma_{s}(\eta(G)) \leq \vert (E(G)-S) \cup v_{2}\vert= q-\Delta^{‘}(G)+1\). Otherwise if \(\lbrace v_{1} \rbrace\) is the cut-vertex , then there exist an edge \(e \in E(G)-S\), \(e\) is incident with \(v_{1}\) such that the corresponding vertices of \(\lbrace(E(G)-S)-e) \cup v_{1}\rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\). Otherwise if \(\lbrace v_{1},v_{2}\rbrace\) are not the cut-vertices then for each vertex \(e_{1}\) in \(\eta(G)\), there exists a vertex \(e_{2} \in E(G)-S\) in \(\eta(G)\), such that the corresponding vertices of \(\lbrace(E(G)-S)-e_{2}) \cup e_{1}\rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G)) \leq q-\Delta^{‘}(G)\).
The result follows from Case (1) and Case (2).
Theorem 2.10.
For any connected graph \(G\), \(\gamma_{se}(\eta(G))\leq q-2, n \geq 3\).
Proof.
Let \(E(G)=\lbrace e_{1},e_{2},…….e_{m}\rbrace\) and let \(A=\lbrace e_{2},e_{3}…..e_{m-1}\rbrace\) with\(\vert A\vert=q-2\). We consider the following cases.
- Case 1:
If \(e_{i} \in E(G)-A\) is not incident with the cut-vertex say \(v_{i}\), then for each \(e_{i} \in E(G)-A\) there exists an edge \(e_{j} \in N(e_{i}) \cap A\) such that the corresponding vertices of \(\lbrace(A-e_{j})\cup e_{i}\rbrace\) in \(\eta(G)\) is dominating set of \(\eta(G)\). Therefore \(\gamma_{s}(\eta(G))\leq \vert A \vert=q-2\).
- Case 2:
If \(e_{i} \in E(G)-A\) is incident with the cut-vertex say \(v_{i}\), then for each \(v_{i},\) there exists an edge \(e_{j}\) which is incident with \(v_{i}\) and \(e_{j} \in A\) such that the corresponding vertices of \(\lbrace (A-e_{j})\cup v_{i}\rbrace\) in \(\eta(G)\) is dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\leq \vert A \vert=q-2\).
Theorem 2.11.
For any connected graph \(G\), \(\gamma_{se}(\eta(G))\leq n-2, n \geq 3\).
Proof.
Let \(V(G)=\lbrace v_{1},v_{2},…….v_{m}\rbrace\),\(A=\lbrace v_{2},v_{3}…..v_{m-1}\rbrace\) with \(\vert A\vert=n-2\). Let \(F\) be the set of edges which is incident with \(\lbrace v_{m-1},v_{m}\rbrace\) and \(B=\lbrace e_{i} /e_{i} \in E(G)-F\rbrace\) with \(\vert B \vert \leq n-2\). We consider the following cases.
- Case 1:
If \(e_{i} \in B\) is not incident with the cut-vertex say \(v_{i}\), then for each \(e_{i} \in E(G)- B\) there exists an edge \(e_{j} \in N(e_{i}) \cap B \) such that the corresponding vertices of \(\lbrace(B-e_{j})\cup e_{i}\rbrace\) is dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\leq \vert B \vert=n-2\).
- Case 2:
If \(e_{i} \in B\) is incident with the cut-vertex say \(v_{i}\), then for each \(v_{i},\) there exists an edge \(e_{j}\) which is incident with \(v_{i}\) and \(e_{j}\in B\) such that the corresponding vertices of \(\lbrace(B-e_{j})\cup v_{i}\rbrace\) is dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\leq \vert B \vert=n-2\).
Theorem 2.12
For any connected graph \(G\), \(\gamma_{e}(G) \leq \gamma_{se}(\eta(G)) \leq \gamma_{e}(G)+\lceil \frac{n}{3}\rceil\).
Proof.
Let \(D\) be the edge dominating set of \(G\). Using Theorem 2.4, we have \(\gamma_{e}(G) \leq \gamma_{se}(\eta(G))\). For the upper bound, Let \(A=\lbrace v_{i}/ v_{i}\) is not incident with any edge of \(D \rbrace\) with \(\vert A \vert \leq \lceil \frac{n}{3} \rceil\). Let \(B=\lbrace e_{i}/e_{i}\) is incident with each \(v_{i},v_{i} \in A \rbrace\) with \(\vert B \vert =\vert A \vert\). We consider the following cases:
- Case 1:If \(G\) is non-separable and for each edge \(e_{i} \in E(G)-D\), there exists an edge \(e_{j} \in N(e_{i}) \cap D\) such that \(\lbrace(D-e_{j}) \cup e_{i}\rbrace\) is the edge dominating set of \(G\), then \(\gamma_{se}(\eta(G))=\vert D \vert =\gamma_{e}(G)\). Otherwise if the corresponding vertices of \(B\) in \(\eta(G)\) does not belong to \(\gamma_{se}(\eta(G))\) set, then there exists atleast one vertex in \(\eta(G)\) which is not covered by any of the corresponding vertex of \(D\) in \(\eta(G)\). Therefore \(B \in \gamma_{se}(\eta(G))\) set. Hence \(\gamma_{se}(G) \leq \vert D \cup B \vert=\gamma_{s}(G)+\lceil \frac{n}{3}\rceil\).
- Case 2: If \(G\) is separable and if for each edge \(e_{i} \in E(G)-D\) there exists an edge \(e_{j} \in N(e_{i}) \cap D\) such that the corresponding vertices of \(\lbrace (D-e_{j}) \cup e_{i}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\) and for each cut-vertex \(v_{i}\), there exists an edge \(e_{m}\) incident with \(v_{i}\) in \(G\) such that the corresponding vertices of \(\lbrace (D-e_{m}) \cup v_{i} \rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G))=\gamma_{e}(G)\). Otherwise if the corresponding vertices of \(B\) in \(\eta(G)\) does not belong to \(\gamma_{s}(\eta(G))\) set, then there exists atleast one vertex in \(\eta(G)\) which is not covered by any vertex corresponding to \(D\) in \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G))\leq \vert D \cup B\vert=\gamma_{e}(G)+\lceil\frac{n}{3}\rceil\).
Theorem 2.13.
For any connected graph \(G\), \(\gamma_{se}(\eta(G)) \leq \gamma_{s}^{‘}(G)+m\), where \(‘m’\) is the number of cut-vertices of \(G\).
Proof.
Let \(D\) be a secure edge dominating set of \(G\) and let \(A=\lbrace v_{i}/G-v_{i}\) is disconnected \(\rbrace\) with \(\vert A\vert=m\). We consider the following cases:
- Case 1: If \(m=0\).
In this case \(\eta(G)=L(G)\), the result is obvious.
- Case 2:
If \( m\neq 0\).
Let \(C\) be the corresponding vertices of \(D\) in \(\eta(G)\) and let \(F=\lbrace e_{i}=(v_{i},v_{j})/e_{i} \in D\) incident with \(v_{i} \in A\rbrace\). We consider the following subcases:
- (i) If \(\vert F \vert \neq \phi\) and if \(v_{j}\) is a not a cut-vertex or \(e_{j} \in N(e_{i}) \in D\), then \(\gamma_{se}(\eta(G))=\gamma_{s}^{‘}(G)\). Otherwise there exists atleast one vertex in \(\eta(G)\) which is not covered by \(C\). Therefore \(A \in \gamma_{se}\) set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G)) \leq \vert C \cup A \vert= \gamma_{s}^{‘}(G)+m\).
- (ii) If \(\vert F \vert =\phi\), then \(v_{i} \in A\) is not covered by any vertex of \(C\). Therefore \(v_{i} \in \gamma_{se}\) set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G)) \leq \vert C \cup A \vert= \gamma_{s}^{‘}(G)+m\)
Theorem 2.14.
For any Tree \(T\), if every vertex is adjacent to support vertex then, \(\gamma_{se}(\eta(T)) \leq \beta_{0}(T)\).
Proof.
Let \(D\) be the maximum vertex independence set of \(T\) and let \(A\) be the \(\gamma_{se}\) set of \(\eta(G)\). Since every vertex is adjacent to an end vertex, then \(A\) will contains all the vertices adjacent to endvertices of \(T\) with \(\vert A \vert \leq \beta_{0}(T)\). Therefore by using Theorem 2.7, we have \(\gamma_{se}(\eta(T)) \leq \beta_{0}(T)\).
Theorem 2.15.
For any connected graph \(G\), \(\gamma_{se}(\eta(G)) \leq \alpha_{0}(G)+m\), where \(‘m’\) is the number of cut-vertices of \(G\).
Proof.
Let \(D\) be the minimum vertex covering set of \(G\) and \(B\) be the set of cut-vertices of \(G\) with \(\vert B \vert=m\). For each vertex \(v_{i} \in D\), choose exactly one edge \(e_{i}\in G, e_{i}\) is incident with \(v_{i}\) such that it covers maximum number of vertices of \(G\). Let \(F\) be the set of all such edges such that \(\vert F \vert =\vert D \vert\). We consider the following cases:
- Case 1: If \(m=0\).
For each edge \(e_{i} \in E(G)-F\), there is an edge \(e_{j} \in F,e_{j} \in N(e_{i})\). Since the corresponding vertices of \(F\) in \(\eta(G)\) will covers all the edges which are incident to \(v_{i} \in V(G)\). Therefore the corresponding vertices of \(\lbrace(F-e_{j})\cup e_{i}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G)) \leq \alpha_{0}(G)\).
- Case 2: If \(m \neq 0\).
Let \(S\) the corresponding vertices of \(F\) in \(\eta(G)\). If \(v_{i} \in B \cap D\), then for each vertex \(v_{i}\), there exists an edge \(e_{j}, e_{j} \in F\) and \(e_{j}\) is incident with \(\lbrace v_{i},v_{j}\rbrace, v_{j}\) is not a cut-vertex, then corresponding vertices of \(\lbrace(F-e_{j}) \cup v_{i} \rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G)) \leq \alpha_{0}(G)\). Otherwise there exists atleast one vertex \(v_{i} \in B \cap V(\eta(G))\) which is not covered by \(S\), therefore \(v_{i} \in \gamma_{se}(\eta(G)\) set of \(\eta(G)\). Therefore \(\gamma_{se}(\eta(G)) \leq \vert D \cup B \vert =\alpha_{0}(G)+m\).
The result follows from Case (1) and Case (2).
Theorem 2.16.
For any connected graph \(G\), \(\gamma_{se}(\eta(G)) \leq \alpha_{1}(G)+m\), where \(m\) is the number of cut-vertices of \(G\).
Proof.
Let \(D\) be the minimum edge covering set of \(G\) and \(B\) be the set of cut-vertices of \(G\) with \(\vert B \vert=m\). We consider the following cases:
- Case 1: If \(e_{i} \in D\) is incident with \(\lbrace v_{1},v_{2} \rbrace\), \((v_{1},v_{2})\notin B\).
For each edge \(e_{j} \in E(G)-D\), there exists an edge \(e_{i} \in D, e_{i} \in N(e_{j})\) and since \(e_{j}\) covers all the edges incident with \(v_{1}\) and \((D-e_{i})\) will covers all the edges incident with \(v_{2}\), therefore the corresponding vertices of \(\lbrace(D-e_{i})\cup e_{j}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G)) \leq \alpha_{1}(G)\).
- Case 2: If \(e_{i} \in D\) is incident with \(\lbrace v_{1},v_{2} \rbrace\), \((v_{1},v_{2})\in B\)
For each edge \(e_{i}\), if there exists an edge adjacent to \(e_{i}\) in \(E(G) \cap D\), then \(\gamma_{s}(\eta(G)) \leq \alpha_{1}(G)\). Otherwise \(\lbrace v_{1}\rbrace\) or \(\lbrace v_{2} \rbrace\) is not covered by any vertices corresponding to \(D\) in \(\eta(G)\). Therefore \(\lbrace v_{1}\) or \(v_{2}\rbrace \in \gamma_{s}(\eta(G))\) set. Hence \(\gamma_{se}(\eta(G))\leq \vert D \cup B \vert =\alpha_{1}(G)+m\).
- Case 3: If \(e_{i} \in D\) is incident with \(\lbrace v_{1},v_{2} \rbrace\), \( \lbrace v_{1}\rbrace \in B\),\(\lbrace v_{2}\rbrace \notin B\)
For each edge \(e_{j} \in E(G)-D\), there exists an edge \(e_{i}, e_{i} \in N(e_{i})\) and since \(e_{j}\) covers all the edges incident with \(v_{1}\) and \((D-e_{i})\) will covers all the edges incident with \(v_{2}\), therefore the corresponding vertices of \(\lbrace(D-e_{i})\cup e_{j}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\) and for \(v_{1}\) there exists an edge \(e_{r} \in D\) incident with \(v_{1}\) such that the corresponding vertices of \(\lbrace (D-v_{1}) \cup e_{r}\rbrace\) in \(\eta(G)\) is the dominating set. Hence \(\gamma_{se}(\eta(G)) \leq \alpha_{1}(G)\).
The result follows from Case (1), Case (2) and Case (3).
Theorem 2.17.
For any connected graph \(G\), \(\gamma_{se}(\eta(G)) \leq \beta_{1}(G)+m\), where \(m\) is the number of cut-vertices of the graph \(G\).
Proof.
Let \(D\) be the maximum edge independence set of \(G\) and \(B\) be the set of cut-vertices of \(G\) with \(\vert B \vert=m\). We consider the following cases:
- Case 1: If \(e_{i} \in D\) is incident with \(\lbrace v_{1},v_{2} \rbrace\), \((v_{1},v_{2})\notin B\).
For each edge \(e_{i}\in E(G)-D\), there exists an edge \(e_{j}\in D, e_{i} \in N(e_{i})\) and since \(e_{j}\) covers all the edges incident with \(v_{1}\) and \((D-e_{i})\) will covers all the edges incident with \(v_{2}\), therefore the corresponding vertices of \(\lbrace(D-e_{i})\cup e_{j}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Hence \(\gamma_{se}(\eta(G)) \leq \beta_{1}(G)\).
- Case 2: If \(e_{i} \in D\) is incident with \(\lbrace v_{1},v_{2} \rbrace\), \((v_{1},v_{2})\in B\)
For each edge \(e_{i}\), if there exists an edge adjacent to \(e_{i}\) in \(E(G) \cap D\), then \(\gamma_{s}(\eta(G)) \leq \beta_{1}(G)\). Otherwise \(\lbrace v_{1}\rbrace\) or \(\lbrace v_{2} \rbrace\) is not covered by any vertices corresponding to \(D\) in \(\eta(G)\). Therefore \(\lbrace v_{1}\) or \(v_{2}\rbrace \in \gamma_{s}(\eta(G))\) set. Hence \(\gamma_{se}(\eta(G))\leq \vert D \cup B \vert =\beta_{1}(G)+m\).
- Case 3: If \(e_{i} \in D\) is incident with \(\lbrace v_{1},v_{2} \rbrace\), \( \lbrace v_{1}\rbrace \in B\),\(\lbrace v_{2}\rbrace \notin B\)
For each edge \(e_{i} \in E(G)-D\), there exists an edge \(e_{j}\in D, e_{i} \in N(e_{i})\) and since \(e_{j}\) covers all the edges incident with \(v_{1}\) and \((D-e_{i})\) will covers all the edges incident with \(v_{2}\), therefore the corresponding vertices of \(\lbrace(D-e_{i})\cup e_{j}\rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\) and for \(v_{1}\) there exists an edge \(e_{r} \in D\) incident with \(v_{1}\) such that the corresponding vertices of \(\lbrace (D-v_{1}) \cup e_{r}\rbrace\) in \(\eta(G)\) is the dominating set of \(G\). Hence \(\gamma_{se}(\eta(G)) \leq \beta_{1}(G)\).
The result follows from Case (1), Case (2) and Case (3).
Theorem 2.18.
For any graph \(G\), \(\gamma(G) \leq \gamma_{se}(\eta(G)\).
Proof.
Let \(D\) be the \(\gamma\) set of \(G\) and let \(B=\lbrace e_{i}/e_{i} \in E(G)\) incident with \(D\) such that it covers maximum number of vertices and \(\vert D \vert=\vert B \vert\). If suppose \(B\) is the secure dominating set of \(G\), then
- (i)
For each \(e_{i} \in E(G)-D\), if there exists an edge \(e_{1} \in D\), \(e_{1} \in N(e_{i})\), such that the corresponding vertices of \(\lbrace(D-e_{1}) \cup e_{i} \rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\).
- (ii)
For each cut-vertex \(c_{i}\in G\), if there exists an edge \(e_{i} \in D\), \(c_{i}\) is incident with \(e_{i}\) in \(G\) such that the corresponding vertices of \(\lbrace (D- \lbrace e_{i} \rbrace) \cup c_{i}\rbrace\) in \(\eta(G)\) is a dominating set of \(\eta(G)\).
Therefore \(\gamma_{se}(\eta(G))=\gamma(G)\). Otherwise the corresponding vertices of \(\lbrace D\cup e_{i} \cup c_{i} \rbrace\) in \(\eta(G)\) is the secure dominating set of \(\eta(G)\). Therefore \(\gamma (G) \leq\gamma_{se}(\eta(G))\).
Theorem 2.19.
For any connected graph \(G\), \(\frac{n}{\Delta+1}\leq \gamma_{se}(\eta(G)) \leq 2q-n\). Furthermore, the upper bound is attained if and only if \(G\) is a path.
Proof.
Since \(\frac{n}{\Delta+1}\leq \gamma(G)\) and using Theorem 2.18. \(\gamma(G) \leq \gamma_{se}(\eta(G))\), the lower bound holds.
For upper bound.
Since \(G\) is connected, \(q \geq n-1\) and by Theorem 2.11, \(\gamma_{se}(\eta(G)) \leq n-2=2(n-1)-n\). Hence \(\gamma_{se}(\eta(G)) \leq 2q-n\).
Now we show that \(\gamma_{se}(\eta(G))=2q-n\) if and only if \(G\) is path. If \(G\) is a path, then by Theorem 2.1(iii), \(\gamma_{se}(\eta(G))=n-2=2(n-1)-n=2q-n\).
conversely, suppose \(\gamma_{se}(\eta(G))=2q-n\). Then by Theorem 2.11, we have \(2q-n \leq n-2\) which implies \(q \leq n-1\). Since \(G\) is connected, \(G\) must be a tree with \(q=n-1\). Thus Theorem 2.5, \(\gamma_{se}(\eta(G)) \leq n-e, e\) is the number of pendent vertices.
If \(e >2\), then \(\gamma_{se}(\eta(G)) \leq n-e < n-2=2q-n\), a contradiction which shows that \(e \leq 2\). But \(G\) is a tree, \(e \geq 2\). Thus \(e=2\) and \(G\) is a path.
Theorem 2.20.
For any subdivision graph \(G\), \(\gamma_{se}(\eta(S(G))\leq 2\alpha_{1}+n_{0}\), where \(n_{0}\) is the number of vertices that subdivides \(E(G)\).
Proof.
Let \(V(G)=\lbrace v_{1},v_{2},v_{3},…,v_{n}\rbrace\) and let \(B=\lbrace n_{j}/n_{j} \in V(S(G))-V(G)\rbrace\) with \(\vert B \vert =n_{0}\). Let \(\alpha_{1}\) be the minimum edge covering set of \(G\) and \(M=\lbrace n_{r}/n_{r} \in B, n_{r}\) in not incident with \(\alpha_{1}\) and \(n_{r}\) is the cut-vertex in \(S(G)\rbrace\) with \(\vert M \vert \leq n_{0}\). Let \(R\) be the set of edges in \(S(G)\) corresponding to the edges in \(\alpha_{1}\) with \(\vert R \vert =2\alpha_{1}\). We consider the following cases:
- Case 1:
If \(\vert M \vert = \phi\).
Then for each edge \(e_{j}=(v_{i},n_{j}) \in E(S(G))-R\), there exists an edge \(e_{i}=(v_{i},n_{j}) \in R \cap N(e_{j})\) such that the corresponding vertices of \(\lbrace(R-e_{i})\cup e_{j}\rbrace\) in \(\eta(S(G))\) is the dominating set of \(\eta(S(G))\) and for each cut-vertex \(v_{i} \in V(S(G))\), there exists an edge \(e_{j}=(v_{i},n_{j}) \in R \),\(e_{j}\) is incident with \(v_{i}\) such that the corresponding vertices of \(\lbrace(R-e_{j})\cup v_{i}\rbrace\) in \(\eta(S(G))\) is the dominating set of \(\eta(S(G))\). Hence \(\gamma_{se}(\eta(S(G))) \leq 2\alpha_{1}\).
- Case 1:
If \(\vert M \vert \neq \phi\).
Now for each cut-vertex say \(v_{m} \in M\), since there is no edge in \(R\) incident with \(v_{m}\) and therefore \(v_{m}\) is not covered by the corresponding vertices of \(R\) in \(\eta(S(G))\). Therefore \(v_{m}\in \gamma_{se}(\eta(S(G))\) set. Hence \(\gamma_{se}(\eta(S(G)))\leq 2\alpha_{1}+n_{0}\).
Proposition 2.21.
For any graph \(G=K_{1,n}\), \(\gamma_{e}(S(G))=n-1\).
Theorem 2.22.
For any graph \(G=K_{1,n}\), \(\gamma_{se}(\eta(S(G)))=n-1\).
Proof.
Let \(V(G)=\lbrace v_{1},v_{2},v_{3},…,v_{n}, d(v_{n})=n-1\rbrace\) and \(E(G)=\lbrace e_{i}=(v_{n},v_{i}), i=1,2,3,…,n-1\rbrace\). Let \(B=\lbrace w_{i}/w_{i}\) is the vertex subdividing \(e_{i}\rbrace\) and \(D=\lbrace (v_{n},w_{i}), i=1,2,3,…,n-1\rbrace\). The corresponding vertices of \(D\) in \(\eta(S(G))\) covers all the vertices of \(\eta(S(G))\) with \(\vert D \vert=n-1\). Now for each edge \((w_{i},v_{i}),i= 1\) to \(n-1\in E(S(G))-D\), there exists an edge \((w_{i},v_{n})\in D \cap N(w_{i},v_{i})\), such that the corresponding vertices of \(\lbrace (D-(w_{i},v_{n})) \cup (w_{i},v_{i}))\rbrace\) in \(\eta(S(G))\) is the dominating set of \(\eta(S(G))\) and for \(v_{n} \in V(S(G))\), there exists an edge \((v_{n},w_{i}), i\) to \(n-1\), incident with \(v_{n}\) such that the corresponding vertices of \(\lbrace(D-(v_{n},w_{i})) \cup v_{n} \rbrace\) in \(\eta(G)\) is the dominating set of \(\eta(G)\). Hence \(\gamma_{s}(\eta(S(G)))=\vert D \vert=n-1\).
Proposition 2.23.
For any graph \(G=K_{n}\), \(\gamma_{e}(S(G))=n-1\).
Theorem 2.24.
For any graph \(G=K_{n}\), \(\gamma_{se}(\eta(S(G)))=n\).
Proof.
Let \(V(G)=\lbrace v_{1},v_{2},v_{3},…,v_{n}\rbrace\) and \(A=\lbrace n_{j}/n_{j} \in V(S(G))-V(G), j=1,2,3,4,5,…,\rbrace\) with \(\vert A \vert =\frac{n(n-1)}{2}\). The set \(B=\lbrace e_{i}=(v_{i},n_{j}), i=1,2,…,n-1, j=1,2,3,4,5,…,\frac{n(n-1)}{2}\rbrace\) such that \(n_{j} \in N(v_{n})\). The corresponding vertices of \(B\) in \(\eta(S(G))\) will covers all the vertices of \(\eta(S(G))\) with \(\vert B\vert=n-1\). Suppose if the corresponding vertices of \(B \notin \gamma_{se}(\eta(S(G))\) set, then there exists atleast one edge \((v_{i},n_{j})\) or \((v_{n},v_{j})\) in \(S(G)\) which is not covered by the corresponding vertices of \(B\) in \(\eta(S(G))\). Now in \(S(G)\), consider the set \(C=\lbrace B \cup (v_{n},n_{j})\rbrace\), then for every edge \(e_{j}=(v_{i},n_{j}) \in E(S(G))-C\) there exists an edge \(e_{k}=(v_{i},n_{j})\in C \cap N(e_{j})\) such that the corresponding vertices of \(\lbrace (C-e_{k})\cup e_{j}\rbrace\) in \(\eta(S(G))\) is the dominating set of \(\eta(S(G))\). Hence \(\gamma_{se}(\eta(S(G)))=n\)
Proposition 2.25.
For any graph \(G=K_{m,n}\), \(\gamma_{e}(S(G))=m+n-1, m \geq n,m,n \geq 2\).
Theorem 2.26.
For any graph \(G=K_{m,n}\), \(\gamma_{se}(\eta(S(G)))=m+n,m \geq n, m \geq 2\).
Proof.
Let \(V(G)=\lbrace v_{1},v_{2},v_{3},…,v_{n}\rbrace\) and \(A=\lbrace n_{j}/n_{j} \in V(S(G))-V(G), j=1,2,3,4,…,\rbrace\) with \(\vert A \vert =mn\). The set \(B=\lbrace (v_{i},n_{j}), d(v_{i})=m, n_{j} \in N(v_{1}),d(v_{1})=n\rbrace\) and \(C=\lbrace (v_{i},n_{j}),d(v_{i})=n,v_{i} \neq v_{1}, n_{j}\in N(v_{2}), d(v_{2})=m\rbrace\). Then the corresponding vertices of \(D=B \cup C\) covers all the vertices of \(S(\eta(S(G)))\) with \(\vert D \vert =m+n-1\). For \(e_{1}=(v_{2},n_{j}) \in E(S(G)-D\), there exists an edge \(e_{2}=(v_{1},n_{j})\) adjacent to \(e_{1}\) such that \(\lbrace(B-e_{2}\cup e_{1}\rbrace\) is a not an edge dominating set of \(S(G)\). Now in \(S(G)\), the set \(E=D \cup (v_{i},n_{j}),d(v_{i})=m, v_{i} \neq v_{n}\), then for every edge \(e_{j}=(v_{i},n_{j} \in E(S(G))-D\) there exists an edge \(e_{k}=(v_{i},n_{j})\in D\) such that \(\lbrace(E-e_{k})\cup e_{j}\rbrace\) is the secure lict dominating set of \(G\). Hence \(\gamma_{se}(S(G))=m+n\)
Proposition 2.27.
For any graph \(G=W_{n}\), \(\gamma_{e}(S(G))=n-1\).
Theorem 2.28.
For any graph \(G=W_{n}\), \(\gamma_{se}(\eta(S(G)))=n\).
Proof.
Let \(V(G)=\lbrace v_{1},v_{2},v_{3},s…,v_{n}, d(v_{n})=n-1\rbrace\) and \(A=\lbrace n_{j}/n_{j} \in V(S(W_{n}))-V(W_{n}), j=1,2,3,4,5,…,2(n-1)\rbrace\) with \(\vert A \vert= 2(n-1)\). The set \(B=\lbrace e_{i}=(v_{i},n_{j}), i=1,2,…,n-1, j=1,2,3,4,5….2(n-1)\rbrace\) such that \(n_{j} \in N(v_{n})\). The corresponding vertices of \(B\) will covers all the vertices of \(\eta(S(G))\) with \(\vert B\vert=n-1\) and therefore \(B\) is the lict dominating set of \(S(G)\). If suppose \(B\) is the secure lict dominating set of \(S(G)\), then there exists atleast one vertex \((v_{n},n_{j})\) or \((v_{i},n_{j}), i=1,2,…,n-1\) in \(\eta(G)\) which is not covered by corresponding vertex of \(B\). Now in \(S(G)\), consider the set \(C=\lbrace B \cup (v_{n},n_{j})\rbrace\), then for every edge \(e_{j}=(v_{i},n_{j}) \in E(S(G)-C\) there exists an edge \(e_{k}=(v_{i},n_{j})\in C \cap N(e_{j})\) such that the corresponding \(\lbrace(C-e_{k})\cup e_{j}\rbrace\) is the lict dominating set of \(S(G)\). Hence \(\gamma_{se}(S(G))=n\)
Theorem 2.29.[3]:For any graph \(G\) of order \(n \geq 3\),
- (i) \(\beta_{1}(G)+ \beta_{1}(\bar G)\leqslant2\lceil\frac{n}{2}\rceil\).
- (ii) \(\beta_{1}(G)*\beta_{1}(\bar G)\leqslant\lceil\frac{n}{2}\rceil^{2}\).
Theorem 2.30.
For any non-separable connected graph \(G\) of order \(n \geq 3\) vertices,
- (i) \(\gamma_{se}(\eta(G))+\gamma_{se}(\eta(\bar G))\leq 2\lceil \frac{n}{2} \rceil\).
- (ii) \(\gamma_{se}(\eta(G))*\gamma_{se}(\eta(\bar G))\leq \lceil \frac{n}{2} \rceil^{2}\).
Proof.
Since \(\beta_{1}(G) \leq \lceil \frac{n}{2} \rceil\), the result follows from 2.17 and using Theorem 2.29.
Competing interests
The authors declare that they have no competing interests.
