n ResultsIn this section, line graph, jump graph, semi-total point graph, semi-total line graph, total graph, quasi-vertex total graph and complementary prism are defined. Cycle and start related Nordhaus-Gaddum type relations of strong efficient dominating sets and the number of strong efficient dominating sets are studied.
Definition 2.1
([12]) The line graph L(G) of G is the graph whose vertex set is E(G) in which two vertices are adjacent if and only if they are adjacent in G.
The following theorem is established first.
Theorem 2.2
L(C_{n}) is strong efficient if and only if n = 3m, m ∈ N. Further$${\gamma}_{se}({C}_{3m})+{\gamma}_{se}\left[L({C}_{3m})\right]=2m\hspace{0.17em}\mathit{and}\hspace{0.17em}\#{\gamma}_{\mathit{se}}({C}_{3m})+\#{\gamma}_{se}\left[L({C}_{3m})\right]=6.$$
ProofLet v_{1}, v_{2}, ..., v_{n} be the vertices and e_{i} = v_{i}v_{i+1}; 1 ≤ i ≤ n − 1, e_{n} = v_{n}v_{1} be the edges of the cycle C_{n}. Obviously L(C_{n}) is a C_{n} with vertices e_{1}, e_{2}, ..., e_{n}.
Therefore by Results 1.4 and 1.5, L(C_{n}) is strong efficient if and only if n = 3m. Therefore γ_{se}(C_{3m}) + γ_{se}[L(C_{3m})] = 2m and by Result 1.17, #γ_{se}(C_{3m}) + #γ_{se}[L(C_{3m})] = 6.
Theorem 2.3
L(K_{1,n}) is strong efficient for all n ≥ 1. Further$${\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[L({K}_{1,n})\right]=2\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\#{\gamma}_{se}({K}_{1,n})+\#{\gamma}_{se}\left[L({K}_{1,n})\right]=n+1.$$
ProofL(K_{1,n}) is strong efficient for all n ≥ 1. Further γ_{se}(K_{1,n})+γ_{se}[L(K_{1,n})] = 2 and #γ_{se}(K_{1,n}) + #γ_{se}[L(K_{1,n})] = n + 1.
Now the concept of jump graph of a graph is defined.
Definition 2.4
([2]) The jump graph J (G) of G is the graph whose vertex set is E(G) in which two vertices are adjacent if and only if they are non-adjacent in G.
Theorem 2.5
J (C_{n}) is strong efficient if and only if n = 3 or n = 4. Moreover$${\gamma}_{se}\left[J({C}_{n})\right]=\{\begin{array}{l}3\hspace{0.17em}if\hspace{0.17em}n=3,\\ 2\hspace{0.17em}if\hspace{0.17em}n=4,\end{array}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{\mathit{se}}\left[J({C}_{n})\right]=\{\begin{array}{l}1\hspace{0.17em}if\hspace{0.17em}n=3,\\ 4\hspace{0.17em}if\hspace{0.17em}n=4.\end{array}$$
ProofLet v_{1}, v_{2}, ..., v_{n} be vertices of C_{n}, and e_{i} = v_{i}v_{i+1} for all 1 ≤ i ≤ n − 1 and e_{n} = v_{n}v_{1} be the edges. Suppose n > 4. For all i with 1 ≤ i ≤ n − 1, e_{1i} is adjacent in J (C_{n}) with all vertices other than e_{i−1} and e_{i+1}, similarliy e_{n} is adjacent with all the vertices other than e_{n−1} and e_{1}. Thus J (C_{n}) is regular of degree n − 3. Suppose J (C_{n}) is strong efficient, and let S be a strong efficient dominating set of J (C_{n}). Suppose further that e_{1} ∈ S. The vertex e_{1} strongly dominates all vertices other than e_{2} and e_{n}, which are adjacent. If e_{2} ∈ S, then |N_{s}[e_{4}] ∩ S| = | {e_{1}, e_{2}} | = 2 > 1, which is a contradicition. Therefore e_{2} ∉ S. If e_{n} ∈ S, then |N_{s}[e_{3}] ∩ S| = | {e_{1}, e_{n}} | = 2 > 1; also a contradicition. Therefore e_{n} ∉ S. This is true for any e_{i} ∈ S, 1 ≤ i ≤ n. Hence J (C_{n}) is not strong efficient when n > 4.
Conversely suppose n ≤ 4. Two cases are considered.
Case (i): Suppose n = 3. J (C_{3}) is 3K_{1} which is obviously strong efficient with the unique strong efficient dominating set {e_{1}, e_{2}, e_{3}}.
Case (ii): Suppose n = 4. J (C_{4}) is 2K_{2} for which {e_{1}, e_{2}},{e_{1}, e_{4}}, {e_{3}, e_{2}} and {e_{3}, e_{4}} are strong efficient dominating sets.
This completes the proof of the theorem.
Theorem 2.6
J (K_{1,n}) is strong efficient for all n ≥ 1. Moreover$${\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[J({K}_{1,n})\right]=n+1\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{\mathit{se}}({K}_{1,n})+\#{\gamma}_{se}\left[J({K}_{1,n})\right]=2.$$
ProofSince J (K_{1,n}) is K̄_{n}, we have γ_{se}[J (K_{1,n})] = n and #γ_{se}[J (K_{1,n})] = 1. Therefore γ_{se}(K_{1,n}) + γ_{se}[J (K_{1,n})] = n + 1 and #γ_{se}(K_{1,n}) + #γ_{se}[J (K_{1,n})] = 2.
Definition 2.7
The paraline graph P L(G) is a line graph of the subdivision graph of G.
Theorem 2.8
PL(C_{n}) is strong efficient if and only if n = 3m, m ∈ N . Further$${\gamma}_{se}({C}_{3m})+{\gamma}_{se}\left[PL({C}_{3m})\right]=3m\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{\mathit{se}}({C}_{3m})+\#{\gamma}_{se}\left[PL({C}_{3m})\right]=6.$$
ProofObviously PL(C_{n}) is C_{2n} and hence from Results 1.4 and 1.5,γ_{se}[P L(C_{3m})] = 2m and by Result 1.17, #γ_{se}[P L(C_{3m})] = 3. Therefore γ_{se}(C_{3m}) + γ_{se}[PL(C_{3m})] = 3m and #γ_{se}(C_{3m}) + #γ_{se}[P L(C_{3m})] = 6.
Theorem 2.9
PL[K_{1,n}] is strong efficient for all n ≥ 1. Further$$\begin{array}{l}{\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[PL({K}_{1,n})\right]=n+1\hspace{0.17em}\hspace{0.17em}\mathit{and}\\ \#{\gamma}_{\mathit{se}}({K}_{1,n})+\#{\gamma}_{se}\left[PL({K}_{1,n})\right]=\{\begin{array}{l}4\hspace{0.17em}if\hspace{0.17em}n=1,\\ n+1\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}\end{array}$$
ProofLet v and v_{i} for 1 ≤ i ≤ n be the vertices if K_{1,n} and let vv_{i} for 1 ≤ i ≤ n be the edges. Let u_{i} be the vertice obtained by subdividing the edge vv_{i} of the star for 1 ≤ i ≤ n. Let e_{i} = vu_{i} and e_{n+1} = u_{i}v_{i} for 1 ≤ i ≤ n be the edges of PL[K_{1,n}].
Case (i): Suppose n = 1. PL[K_{1,1}] is P_{2} which is obviously strong efficient and hence γ_{se}[PL(K_{1,1})] = 1 and #γ_{se}[PL(K_{1,1})] = 2.
Case (ii): Suppose that n > 1, that ∆P L[K_{1,n}] = deg(e_{i}) = n for 1 ≤ i ≤ n and that deg(e_{j}) = 1; n + 1 ≤ j ≤ 2n. We see that e_{1} is adjacent with the ${e}_{j}^{s}$ for 2 ≤ j ≤ n + 1. Hence e_{1} strongly dominates all of these vertices. Also, the vertices e_{n+j} for 2 ≤ j ≤ n are muthually non-adjacent. Therefore {e_{1}, e_{n+2}, e_{n+3}, · · · , e_{2n}} is a strong efficient dominating set of P L[K_{1,n}]. Similarly {e_{2}, e_{n+1}, e_{n+3}, e_{n+4}, · · · , e_{2n}}, {e_{3}, e_{n+1}, e_{n+2}, e_{n+4}, e_{n+5}, · · · , e_{2n}} , · · · , {e_{n}, e_{n+1}, e_{n+2}, · · · , e_{2n−1}} is also a strong efficient dominating set of P L(K_{1,n}).
Therefore γ_{se}[P L(K_{1,n})] = n and $\#{\gamma}_{se}\left(PL\left[{K}_{1,n}\right]\right)=\{\begin{array}{l}2\hspace{0.17em}if\hspace{0.17em}n=1,\\ n\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}$
Therefore γ_{se}(K_{1,n}) + γ_{se}[P L(K_{1,n})] = n + 1 and $$\#{\gamma}_{se}({K}_{1,n})+\#{\gamma}_{se}\left[PL\left({K}_{1,n}\right)\right]=\{\begin{array}{l}4\hspace{0.17em}if\hspace{0.17em}n=1,\\ n+1\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}$$
Definition 2.10
([9]) The semi-total point graph T_{2}(G) is the graph whose vertex set is V (G) ∪ E(G) where two vertices are adjacent if and only if
Theorem 2.11
T_{2}(C_{n}) is strong efficient if and only if n = 3m for m ∈ N. Further$${\gamma}_{se}({C}_{3m})+{\gamma}_{se}\left[{T}_{2}({C}_{3m})\right]=3m\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{\mathit{se}}({C}_{3m})+\#{\gamma}_{se}\left[{T}_{2}({C}_{3m})\right]=6.$$
ProofLet v_{1}, v_{2}, ..., v_{n} be the vertices and e_{i} = v_{i}v_{i+1} for 1 ≤ i ≤ n − 1, as well as e_{n} = v_{n}v_{1} be the edges of the cycle C_{n}. Let n ≠ 3m. Suppose T_{2}(C_{n}) is strong efficient. Let S be a strong efficient dominating set of T_{2}(C_{n}).
Case (i): Let n = 3m + 1. ∆[T_{2}(C_{3m+1})] = deg(v_{i}) = 4, deg(e_{i}) = 2; 1 ≤ i ≤ 3m + 1. Suppose v_{1} ∈ S. We have that v_{1} strongly dominates the vertices v_{2}, v_{3m+1}, e_{1} and e_{3m+1}. Similarly v_{3i−2} strongly dominates v_{3i−3}, v_{3i−1}, e_{3i−3} and e_{3i−2}; 2 ≤ i ≤ m. If v_{3m} ∈ S, then |N_{s}[V_{3m+1}] ∩ S| = | {v_{1}, v_{3m}} | = 2 > 1. This is a contradicition. Therefore v_{3m} ∉ S. Hence there is no vertex in S that strongly efficiently dominates V_{3m}. Hence T_{2}(C_{3m+1}) is not strong efficient.
Case (ii): Let n = 3m + 2, and observe that ∆[T_{2}(C_{3m+2})] = deg(v_{i}) = 4 and deg(e_{i}) = 2 for 1 ≤ i ≤ 3m + 2. Suppose v_{1} ∈ S. The vertex v_{1} strongly dominates the vertices v_{2}, v_{3m+2}, e_{1} and e_{3m+2}. Similarly v_{3i−2} strongly dominates v_{3i−3}, v_{3i−1}, e_{3i−3} and e_{3i−2} for 2 ≤ i ≤ m. Moreover, v_{3m} and v_{3m+1} are adjacent.
Subcase (ii a): Suppose v_{3m} ∈ S. Then |N_{s}[V_{3m−1}] ∩ S| = | {v_{3m}, v_{3m−2}} | = 2 > 1. This is also a contradicition. Therefore v_{3m} ∉ S.
Subcase (ii b): Suppose v_{3m+1} ∈ S. Then |N_{s}[V_{3m+2}] ∩ S| = | {v_{1}, v_{3m+1}} | = 2 > 1. This is also a contradicition. Therefore v_{3m+1} ∉ S. Hence there is no vertex in S to strongly efficiently dominate V_{3m+1}. Therefore T_{2}(C_{n}) is not strong efficient when n = 3m + 1 or 3m + 2.
Conversely suppose n = 3m. Then ∆[T_{2}(C_{3m})] = deg(v_{i}) = 4 and deg(e_{i}) = 2 for 1 ≤ i ≤ 3m. Also, ${e}_{i}^{s}$ are non-adjacent. For 1 ≤ i ≤ m the vertex v_{3i−2} strongly dominate all the vertices other than e_{3i−1}. The vertices e_{3i−1} for 1 ≤ i ≤ m are strongly dominated by themselves. Hence {v_{3i−2}, e_{3i−1}; 1 ≤ i ≤ m} is a strong efficient dominating set of T_{2}(C_{3m}). By symmetry, {v_{3i−1}, e_{3i}; 1 ≤ i ≤ m} and {v_{3i}, e_{3i−2}; 1 ≤ i ≤ m} are also strong efficient dominating sets of T_{2}(C_{n}).
Therefore γ_{se}[T_{2}(C_{3m})] = 2m and #γ_{se}[T_{2}(C_{3m})] = 3.
Hence γ_{se}(C_{3m}) + γ_{se}[T_{2}(C_{3m})] = 3m and #γ_{se}(C_{3m}) + #γ_{se}[T_{2}(C_{3m})] = 6
Now the following theorem is established.
Theorem 2.12
T_{2}(K_{1,n}) is strong efficient for all n ≥ 1. Further$$\begin{array}{l}{\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[{T}_{2}({K}_{1,n})\right]=2\hspace{0.17em}\hspace{0.17em}\mathit{and}\\ \#{\gamma}_{\mathit{se}}({K}_{1,n})+\#{\gamma}_{se}\left[{T}_{2}({K}_{1,n})\right]=\{\begin{array}{l}5\hspace{0.17em}if\hspace{0.17em}n=1,\\ 2\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}\end{array}$$
ProofLet v and v_{i} for 1 ≤ i ≤ n be the vertices and e_{i} = vv_{i} for 1 ≤ i ≤ n be the edges of the star K_{1,n}.
Case (i): Suppose n = 1. Then T_{2}(K_{1,1}) is the cycle c_{3} for which {e_{1}}, {v}, {v_{1}} are the strong efficient dominating sets. Hence γ_{se}[T_{2}(K_{1,1})] = 1 and #γ_{se}[T_{2}(K_{1,1})] = 3.
Case (ii): Suppose n > 1. In T_{2}(K_{1,n}), v is adjacent with all the ${v}_{i}^{s}$ and ${e}_{i}^{s}$; 1 ≤ i ≤ n. Thus v is the unique full degree vertex. Therefore, by Result 1.1, γ_{se}[T_{2}(K_{1,n})] = 1 and #γ_{se}[T_{2}(K_{1,n})] = 1.
Therefore γ_{se}(K_{1,n}) + γ_{se}[T_{2}(K_{1,n})] = 2 and $\#{\gamma}_{se}({K}_{1,n})+\#{\gamma}_{se}\left[{T}_{2}({K}_{1,n})\right]=\{\begin{array}{l}5\hspace{0.17em}if\hspace{0.17em}n=1,\\ 2\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}$
Definition 2.13
([9]) The semi-total line graph T_{1}(G) is the graph whose vertex set is V (G) ∪ E(G) where two vertices are adjacent if and only if
Theorem 2.14
T_{1}(C_{n}) is strong efficient if and only if n = 3m, m ∈ N . Further$${\gamma}_{se}({C}_{3m})+{\gamma}_{se}\left[{T}_{1}({C}_{3m})\right]=3m\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{\mathit{se}}({C}_{3m})+\#{\gamma}_{se}\left[{T}_{1}(C3m)\right]=6.$$
ProofT_{1}(C_{n}) is obtained from T_{2}(C_{n}) by replacing v_{i} and e_{i}. Hence the result follows from Theorem 2.11.
Theorem 2.15
T_{1}(K_{1,n}) is strong efficient for all n ≥ 1. Further$$\begin{array}{l}{\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[{T}_{1}({K}_{1,n})\right]=n+1,\hspace{0.17em}\hspace{0.17em}if\hspace{0.17em}n\ge 1\hspace{0.17em}\hspace{0.17em}\mathit{and}\\ \#{\gamma}_{\mathit{se}}({K}_{1,n})+\#{\gamma}_{se}\left[{T}_{1}({K}_{1,n})\right]=\{\begin{array}{l}3\hspace{0.17em}if\hspace{0.17em}n=1,\\ n+1\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}\end{array}$$
ProofLet v and v_{i} for 1 ≤ i ≤ n be the vertices and e_{i} = vv_{i} for 1 ≤ i ≤ n be the edges of the star K_{1,n}.
T_{1}(K_{1,1}) is P_{3} which is strong efficient and γ_{se}[T_{1}(K_{1,1})] = 1. Thus #γ_{se}(K_{1,n}) + #γ_{se}[T_{1}(K_{1,n})] = 3
Suppose n ≥ 2. In T_{1}(K_{1,n}), we have deg(v) = n, deg(v)_{i} = 1, and deg(e_{i}) = n + 1 = ∆[T_{1}(K_{1,n})] for 1 ≤ i ≤ n. Each e_{i} strongly uniquely dominates v and all v_{j}’s for j ≠ i.
Hence {e_{i}, v_{j}|j ≠ i, 1 ≤ j ≤ n} for 1 ≤ i ≤ n, form strong efficient dominating sets of T_{1}(K_{1,n}). Therefore T_{1}(K_{1,n}) is strong efficient and γ_{se}(K_{1,n}) = n, if n ≥ 1. #γ_{se}[T_{1}(K_{1,n})] = n. Hence #γ_{se}(K_{1,n}) + #γ_{se}[T_{1}(K_{1,n})] = n + 1 if n > 1
Definition 2.16
The total graph T (G) of a graph G is the graph with vertex set V (G) ∪ E(G) where two vertices are adjacent if and only if
(i) they are adjacent vertices of G or
(ii) they are adjacent edges of G or
(iii) one is a vertex of G and the other is an edge of G incident with it.
Theorem 2.17
T (C_{n}) is strong efficient if and only if n = 5m, m ∈ N. Further$${\gamma}_{se}\left[T({C}_{5m})\right]=2m\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{\mathit{se}}\left[T({C}_{5m})\right]=5.$$
ProofLet v_{1}, v_{2}, . . . , v_{n} be the vertices and e_{i} = v_{i}v_{i+1} for 1 ≤ i ≤ n − 1 and e_{n} = v_{n}v_{1} be the edges of the cycle C_{n}. In T (C_{n}), v_{i} is adjacent with v_{i+1}, v_{i−1}, e_{i} and e_{i−1} for 2 ≤ i ≤ n − 1. We have that e_{i} is adjacent with e_{i−1}, e_{i+1}, v_{i} and v_{i+1} for 2 ≤ i ≤ n − 1, and that v_{1} is adjacent with v_{2}, v_{n}, e_{1} and e_{n}. The vertex v_{n} is adjacent with v_{n−1}, v_{1}, e_{n−1} and e_{n}. The vertex e_{1} is adjacent with e_{2}, e_{n}, v_{1} and v_{2}. The vertex e_{n} is adjacent with v_{n}, v_{1}, e_{n−1} and e_{1}. Hence deg(v_{i}) = deg(e_{i}) = 4 for 1 ≤ i ≤ n. Therefore T (C_{n}) is regular of degree 4. Suppose n ≠ 5m. Suppose T (C_{n}) is strong efficient. Let S be a strong efficient dominating set.
Case (i): Let n = 5m+1. Suppose v_{5i−4}, e_{5i−2} ∈ S for 1 ≤ i ≤ m. Then v_{5i−4}, e_{5i−2} for 1 ≤ i ≤ m strongly dominates all the vertices other than v_{5m} and e_{5m}. Also v_{5m} and e_{5m} are adjacent. If v_{5m} ∈ S, then |N_{s}[V_{5m+1}] ∩ S| = | {v_{1}, v_{5m}} | = 2 > 1. This is a contradicition. Therefore v_{5m} ∉ S. If e_{5m} ∈ S, then |N_{s}[v_{5m+1}] ∩ S| = | {v_{1}, e_{5m}} | = 2 > 1. This is also a contradiction. Therefore e_{5m} ∉ S. This is for any v_{i} ∈ S. Therefore T (C_{n}) is not strong efficient when n = 5m + 1 for m ∈ N.
Case (ii): Let n = 5m + 2. Suppose v_{5i−4}, e_{5i−2} ∈ S for 1 ≤ i ≤ m. As before v_{5i−4}, e_{5i−2} for 1 ≤ i ≤ m strongly dominates all the vertices other than v_{5m+1}, v_{5m} and e_{5m}. Also v_{5m+1}, v_{5m} and e_{5m} are mutually adjacent. If v_{5m+1} ∈ S, then |N_{s}[V_{5m+2}] ∩ S| = | {v_{1}, v_{5m+1}} | = 2 > 1. This is a contradicition. Therefore v_{5m+1} ∉ S. If v_{5m} ∈ S, then |N_{s}[V_{5m−1}] ∩ S| = | {v_{5m}, e_{5m−2}} | = 2 > 1. This is a contradicition. Therefore v_{5m} ∉ S. If e_{5m} ∈ S, then |N_{s}[e_{5m−1}] ∩ S| = | {e_{5m}, e_{5m−2}} | = 2 > 1. This is a contradicition. Therefore e_{5m} ∉ S. If e_{5m+1} ∈ S, then |N_{s}[e_{5m+2}] ∩ S| = | {v_{1}, e_{5m+1}} | = 2 > 1. This is also a contradicition. Therefore e_{5m+1} ∉ S. Therefore e_{5m} ∉ S. This is for any v_{i} ∈ S. Therefore T (C_{n}) is not strong efficient when n = 5m + 2, m ∈ N .
Case (iii): Let n = 5m + 3. Suppose v_{5i−4}, e_{5i−2} ∈ S for 1 ≤ i ≤ m. Then v_{5i−4}, e_{5i−2} for 1 ≤ i ≤ m strongly dominates all the vertices other than e_{5m+2}. If e_{5m+2} ∈ S, then |N_{s}[V_{5m+3}] ∩ S| = | {v_{1}, e_{5m+2}} | = 2 > 1. This is also a contradicition. Therefore e_{5m+2} ∉ S. Therefore e_{5m} ∉ S. This is for any v_{i} ∈ S. Therefore T (C_{n}) is not strong efficient when n = 5m + 3, m ∈ N .
Case (iv): Let n = 5m + 4. Suppose v_{5i−4}, e_{5i−2} ∈ S; 1 ≤ i ≤ m. As before v_{5i−4}, e_{5i−2}; 1 ≤ i ≤ m strongly dominates all the vertices other than v_{5m+3}, e_{5m+2} and e_{5m+3}. If v_{5m+3} ∈ S, then |N_{s}[v_{5m+4}] ∩ S| = | {v_{1}, v_{5m+3}} | = 2 > 1. This is a contradicition. Therefore v_{5m+3} ∉ S. If e_{5m+2} ∈ S, then |N_{s}[e_{5m+1}] ∩ S| = | {v_{5m+1}, e_{5m+2}} | = 2 > 1. This is also a contradicition. Therefore e_{5m+2} ∉ S. If e_{5m+3} ∈ S, then |N_{s}[v_{5m+4}] ∩ S| = | {e_{5m+3}, v_{1}} | = 2 > 1. This is also a contradicition. Therefore e_{5m+3} ∉ S. Therefore e_{5m} ∉ S. This is for any v_{i} ∈ S. Therefore T (C_{n}) is not strong efficient when n = 5m + 4, m ∈ N .
Case (v): Let n = 4. Suppose v_{1} ∈ S. v_{1} strongly dominates v_{2}, v_{4}, e_{1} and e_{4}. If e_{2} or v_{3} belongs to S then v_{2} is strongly dominated by two vertices v_{1} and e_{2} or v_{1}and v_{3} respectively. If e_{3} belongs to S then v_{4} is strongly dominated by two vertices v_{1} and e_{3}. Therefore e_{2}, e_{3} and v_{3} do not belong to S. There is no vertex in S to strongly dominate these three vertices, a contradiction. This is true if any v_{i} or e_{i} belong to S. Hence T (C_{n}) is not strong efficient when n = 4.
Case (vi): Let n = 3. Suppose v_{1} ∈ S. v_{1} strongly dominates all the vertices other than e_{2}. If e_{2} belongs to S then all the vertices other than v_{1} are strongly dominated by two vertices v_{1} and e_{2}. Therefore e_{2} ∉ S. Hence there is no vertex in S to strongly dominate e_{2}, a contradiction. This is true if any v_{i} or e_{i} belong to S. Hence T (C_{n}) is not strong efficient when n = 3.
Conversely suppose n = 5m. In T (C_{5m}), v_{5i−4} strongly dominates the vertices v_{5i−3}, e_{5i−4}, e_{5m} and v_{5i−1}; 1 ≤ i ≤ m. Similarly e_{5i−2} strongly dominates the vertices e_{5i−3}, e_{5i−1}, v_{5i−2} and v_{5i−1}; 1 ≤ i ≤ m. Hence {v_{5i−4}, e_{5i+2}; 1 ≤ i ≤ m} are also strong efficient dominating sets of T (C_{5m}). Therefore γ_{se}[T (C_{5m})] = 2m and #γ_{se}[T (C_{5m})] = 5, m ∈ N .
Theorem 2.18
T (K_{1,n}) is strong efficient for all n ≥ 1. Further$$\begin{array}{l}{\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[T({K}_{1,n})\right]=2\hspace{0.17em}\hspace{0.17em}\mathit{and}\\ \#{\gamma}_{\mathit{se}}({K}_{1,n})+\#{\gamma}_{se}\left[T({K}_{1,n})\right]=\{\begin{array}{l}5\hspace{0.17em}if\hspace{0.17em}n=1,\\ 2\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}\end{array}$$
ProofLet v and v_{i} for 1 ≤ i ≤ n be the vertices and e_{i} = vv_{i} be the edges of the star K_{1,n}.
Case (i): Suppose n = 1. T (K_{1,1}) is a cycle C_{3} for which {e_{1}}, {v}, {v_{1}} are the strong efficient dominating set.
Hence γ_{se}[T (K_{1,1})] = 1 and #γ_{se}[T (K_{1,1})] = 3.
Case (ii): Suppose n > 1. In T (K_{1,n}), v is adjacent with all ${v}_{i}^{s}$ and ${e}_{i}^{s}$ for 1 ≤ i ≤ n.
Hence v is the unique full degree vertex, deg(v_{i}) = 2, deg(e_{i}) = 1 + i for 1 ≤ i ≤ n.
By Result 1.1, γ_{se}[T (K_{1,n})] = 1 and #γ_{se}[T (K_{1,n})] = 1.
Therefore γ_{se}(K_{1,n}) + γ_{se}[T (K_{1,n})] = 2 and $$\#{\gamma}_{se}({K}_{1,n})+\#{\gamma}_{se}\left[T({K}_{1,n})\right]=\{\begin{array}{l}5\hspace{0.17em}if\hspace{0.17em}n=1,\\ 2\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}$$
Definition 2.19
([11]) The quasi-total graph P (G) is the graph with vertex set V (G) ∪ E(G) where two vertices are adjacent if and only if
(i) they are non adjacent vertices of G or
(ii) they are adjacent edges of G or
(iii) one is a vertex of G and the other is an edge of G incident with it.
Theorem 2.20
P (C_{n}) is strong efficient if and only if n = 3. Further$${\gamma}_{se}\left[P({C}_{n})\right]=2\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\hspace{0.17em}\#{\gamma}_{se}\left[P({C}_{n})\right]=3.$$
ProofLet v_{1}, v_{2}, ..., v_{n} be the vertices and e_{i}= v_{i}v_{i+1} for 1 ≤ i ≤ n − 1, e_{n}= v_{n}v_{1} be the edges of the cycle C_{n}. Let n > 3. Suppose P (C_{n}) is strong efficient. Let S be a strong efficient dominating set of P (C_{n}).
Case (i): Let n = 4.∆[P (C_{4})] = deg(e_{i}) = 4, deg(v_{i}) = 3; 1 ≤ i ≤ 4. Suppose e_{1} ∈ S. The vertex e_{1} strongly dominates all the vertices other than e_{3}, v_{3} and v_{4}. If e_{3} ∈ S, then |N_{s}[e_{2}] ∩ S| = | {e_{1}, e_{3}} | = 2 > 1. This is a contradicition. Therefore e_{3} ∉ S. If v_{3} ∈ S, then |N_{s}[v_{1}] ∩ S| = | {e_{1}, v_{3}} | = 2 > 1. This is a contradicition. Therefore v_{3} ∉ S. If v_{4} ∈ S, then |N_{s}[v_{2}] ∩ S| = | {e_{1}, v_{4}} | = 2 > 1. This is also a contradicition. Therefore v_{4} ∉ S. Therefore P (C_{4}) is not strong efficient.
Case (ii): Let n = 5. In P (C_{5}), deg(v_{i}) = deg(e_{i}) = 4 for 1 ≤ i ≤ 5. Suppose e_{1} ∈ S. The vertex e_{1} strongly dominates v_{2}, e_{2}, v_{1} and e_{5}. If either v_{3} or e_{3} belong to S, then e_{2} is dominated by two elements v_{3}, e_{1} or e_{3}, e_{1} of S respectively, a contradiction. Therefore v_{3} and e_{3} do not belong to S. If v_{4} ∈ S, then v_{2} is dominated by two elements v_{4} and e_{1}, a contradiction. Therefore v_{4} doesnot belong to S. If either v_{5} or e_{4} belong to S, then e_{5} is dominated by two elements v_{5}, e_{1} or e_{4}, e_{1} of S respectively, a contradicition. Therefore v_{5} and e_{4} do not belong to S. Hence P (C_{5}) is not efficient.
Case (iii): Let n > 5. Then ∆[P (C_{n})] = deg(v_{i}) = n − 1, and deg(e_{i}) = 4 for 1 ≤ i ≤ 4. The vertex v_{i} strongly dominates all the ${v}_{j}^{s}$ other than v_{i−1} and v_{i+1}. Also v_{i−1} and v_{i+1} are adjacent. If v_{i−1} ∈ S, then |N_{s}[v_{i−3}] ∩ S| = | {v_{i}, v_{i−1}} | = 2 > 1. This is a contradicition. Therefore v_{i−1} ∉ S. If v_{i+1} ∈ S, then |N_{s}[v_{i+3}] ∩ S| = | {v_{i}, v_{i+1}} | = 2 > 1. This is also a contradicition. Therefore v_{i+1} ∉ S. Therefore P (C_{n}) is not strong efficient when n > 3.
Conversely suppose n = 3. Obviously {e_{1}, v_{3}} , {e_{2}, v_{1}} and {e_{1}, v_{3}} are strong efficient dominating sets P (C_{3}). Therefore γ_{se}[P (C_{3})] = 2 and #γ_{se}[P (C_{3})] = 3.
Theorem 2.21
P (K_{1,n}) is strong efficient if and only if n = 1. Further$${\gamma}_{se}\left[P({K}_{1,1})\right]=\#{\gamma}_{se}\left[P({K}_{1,n})\right]=1.$$
ProofLet v, v_{1}, v_{2}, ..., v_{n} be the vertices and e_{i} = vv_{i} for 1 ≤ i ≤ n be the edges of the star K_{1,n}. Suppose n > 1. Let P (K_{1,n}) be strong efficient and let S be a strong efficient dominating set of P (K_{1,n}).
In P (K_{1,n}) the vertex v_{i} is adjacent with all other ${v}_{j}^{s}$ and e_{i} for 1 ≤ i ≤ n. Therefore deg(v_{i}) = n. Also e_{i} is adjacent with all other ${e}_{j}^{s}$, v_{i} and v for 1 ≤ i ≤ n. Therefore deg(e_{i}) = n + 1. Similarily v is adjacent with all other ${e}_{j}^{s}$ for 1 ≤ i ≤ n. Therefore deg(v) = n. Suppose e_{i} ∈ S. Then e_{i} strongly dominates all other ${e}_{j}^{s}$, v_{i} and v; 1 ≤ i ≤ n. Suppose v_{j} ∈ S, j ≠ i, then |N_{s}[v_{i}] ∩ S| = | {e_{i}, v_{j}} | = 2 > 1. This is a contradicition. Therefore v_{j} ∉ S. Therefore P (K_{1,n}) is not strong efficient if n > 1.
Conversely suppose n = 1. Then P (K_{1,1}) is P_{3} which is obviously strong efficient with the unique strong efficient dominating set {e_{1}}. Therefore γ_{se}[P (K_{1,1})] = #γ_{se}[P (K_{1,1})] = 1.
Definition 2.22
([11]) The quasi vertex-total graph Q(G) is the graph with vertex set V (G) ∪ E(G) where two vertices are adjacent if and only if
(i) they are adjacent vertices of G or
(ii) they are nonadjacent vertices of G or
(iii) they are adjacent edges of G or
(iv) one is a vertex of G and the other is an edge of G incident with it.
Theorem 2.23
Q(C_{n}) is strong efficient if and only if n = 3m + 2, m ∈ N. Further$${\gamma}_{se}\left[Q({C}_{3m+2})\right]=m+1\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\#{\gamma}_{se}\left[Q({C}_{3m+2})\right]=3m+2.$$
ProofLet v_{1}, v_{2}, ..., v_{n} be the vertices and e_{i} = v_{i}v_{i+1} for 1 ≤ i ≤ n − 1, e_{n} = v_{n}v_{1} be the edges of the cycle C_{n}. Let n ≠ 3m + 2, m ∈ N . Suppose Q(C_{n}) is strong efficient. Let S be a strong efficient dominating set of Q(C_{n}).
Case (i): Suppose n = 3m, m ∈ N . We have ∆[Q(C_{3m})] = deg(v_{i}) = 3m + 1 and deg(e_{i}) = 4; 1 ≤ i ≤ 3m. Suppose v_{1} ∈ S. Then v_{1} strongly dominates all other ${v}_{j}^{s}$, e_{3m} and e_{1}. The remaining $\left(3m-2\right){e}_{j}^{s}$ which are adjacent with v_{j} and v_{j+1} form a path of length 3m − 2. Obviously e_{3}, e_{6}, e_{9}, · · · , e_{3m−3} strongly dominates all the ${e}_{j}^{s}$ except e_{3m−1} If e_{3m−1} ∈ Sthen |N_{s}[e_{3m}] ∩ S| = | {e_{3m−1}, v_{1}} | = 2 > 1. This is a contradicition. Therefore e_{3m−1} ∉ S. Therefore Q(C_{n}) is not strong efficient when n = 3m for m ∈ N .
Case (ii): Suppose n = 3m + 1 for m ∈ N. ∆[Q(C_{3m+1})] = deg(v_{i}) = 3m + 2 and deg(e_{i}) = 4 for 1 ≤ i ≤ 3m + 1. Suppose v_{1} ∈ S. Then v_{1} strongly dominates all other ${v}_{j}^{s}$, e_{3m+1} and e_{1}. The remaining $\left(3m-1\right){e}_{j}^{s}$ which are adjacent with v_{j} and v_{j+1} form a path of length 3m − 1. Obviously e_{3}, e_{6}, e_{9}, · · · , e_{3m−3} strongly dominates all the ${e}_{j}^{s}$ except e_{3m} and e_{3m−1}. If e_{3m} ∈ S, then |N_{s}[e_{3m+1}] ∩ S| = | {e_{3m}, v_{1}} | = 2 > 1. This is a contradicition. Therefore e_{3m} ∉ S. If e_{3m−1} ∈ S, then |N_{s}[e_{3m−2}]∩S| = | {e_{3m−1}, e_{3m−3}} | = 2 > 1. This is also a contradicition. Therefore e_{3m−1} ∉ S. Therefore Q(C_{n}) is not strong efficient if n = 3m or 3m + 1, m ∈ N .
Conversely suppose n = 3m + 2 for m ∈ N . Then ∆[Q(C_{3m+2})] = deg(v_{i}) = 3m + 3 and deg(e_{i}) = 4 for 1 ≤ i ≤ 3m + 2. Suppose v_{1} ∈ S. We see that v_{1} strongly dominates all other ${v}_{j}^{s}$, e_{3m+2} and e_{1}. The remaining 3m vertices ${e}_{j}^{s}$ which are adjacent with v_{j} and v_{j+1} form a path of length 3m. Obviously e_{3}, e_{6}, e_{9}, · · · , e_{3m} strongly dominates all the remaining ${e}_{j}^{s}$. Hence {v_{1}, e_{3}, e_{6}, e_{9}, · · · , e_{3m}} is a strong efficient dominating set. Similarly {v_{2}, e_{4}, e_{7}, e_{10}, · · · , e_{3m+1}},{v_{3}, e_{5}, e_{8}, e_{10}, · · · , e_{3m+2}}{v_{4}, e_{6}, e_{9}, e_{12}, · · · , e_{3m}, e_{1}},{v_{5}, e_{7}, e_{10}, e_{13}, · · · , e_{3m+1}, e_{2}} · · · and {v_{3m+2}, e_{2}, e_{5}, e_{8} , · · · , e_{3m−1}} are also strong efficient dominating sets.
Therefore γ_{se}[Q(C_{3m+2})] = m + 1 and #γ_{se}[Q(C_{3m+2})] = 3m + 2, m ∈ N .
Theorem 2.24
Q(K_{1,n}) is strong efficient for all n ≥ 1. Further$$\begin{array}{l}{\gamma}_{se}({K}_{1,n})+{\gamma}_{se}\left[Q({K}_{1,n})\right]=2\hspace{0.17em}\hspace{0.17em}\mathit{and}\\ \#{\gamma}_{\mathit{se}}({K}_{1,n})+\#{\gamma}_{se}\left[Q({K}_{1,n})\right]=\{\begin{array}{l}5\hspace{0.17em}if\hspace{0.17em}n-1,\\ 2\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}\end{array}$$
ProofLet v and v_{i} for 1 ≤ i ≤ n be the vertices and e_{i}= vv_{i} be the edges of the star K_{1,n}. If n = 1, then Q(K_{1,1}) is a cycle C_{3}. So γ_{se}[Q(K_{1,1})] = 1 and #γ_{se}[Q(K_{1,1})] = 3. So let n > 1. In Q(K_{1,n}), v is adjacent with all ${v}_{i}^{s}$ and ${e}_{i}^{s}$ for 1 ≤ i ≤ n. Then v is the unique full degree vertex. Therefore by Result 1.1, γ_{se}[Q(K_{1,n})] = 1 and #γ_{se}[Q(K_{1,n})] = 1. Therefore γ_{se}(K_{1,n}) + γ_{se}[Q(K_{1,n})] = 2 and $$\#{\gamma}_{se}({K}_{1,n})+\#{\gamma}_{se}\left[Q({K}_{1,n})\right]=\{\begin{array}{l}5\hspace{0.17em}if\hspace{0.17em}n=1,\\ 2\hspace{0.17em}if\hspace{0.17em}n>1.\end{array}$$
Definition 2.25
([6]) For a graph G, the complementary prism, donoted by GḠ, is formed from a copy of G and a copy of Ḡ by adding a perfect matching between corresponding vertices.
Theorem 2.26
C_{n}C̄_{n}is strong efficient if and only if n = 3. Moreover γ_{se}[C_{n}C̄_{n}] = 3 and #γ_{se}[C_{n}C̄_{n}] = 3.
ProofLet v_{1}, v_{2}, ..., v_{n}be the vertices of the cycle C_{n}and v̄_{1}, v̄_{2}, · · ·, v̄_{n}be the vertices in the copy of C̄_{n}. Let n > 3.
Case (i): Suppose n = 4 or n = 5. The graph C_{4}C̄_{4} and C_{5}C̄_{5} are shown in Fig 1. The subgraph induced by the maximum degree vertices is C_{4}, which is not strong efficient. Hence C_{4}C̄_{4} is not strong efficient. C_{5}C̄_{5} is the Peterson graph which is not efficient. Hence C_{5}C̄_{5} is not strong efficient.
Case (ii): Suppose C_{n}C̄_{n} is strong efficient. Let S be a strong efficient dominating set of C_{n}C̄_{n} Suppose first n > 5. Then ∆[C_{n}C̄_{n}] = deg(v̄_{i}) = n − 2 for 1 ≤ i ≤ n and deg(v_{i}) = 3 for 1 ≤ i ≤ n. Moreover v̄_{1} and v̄_{n} are non-adjacent. Suppose v̄_{1} ∈ S and observe that v̄_{1} strongly dominates v_{1} and all v̄_{i} other than v̄_{2} and v̄_{n}. Therefore v̄_{2} ∈ S. So |N_{s}[v̄_{4}] ∩ S| = | {v̄_{1}, v̄_{2}} | = 2 > 1. This is a contradicition. Therefore v̄_{2} ∉ S. If v̄_{n} ∈ S, then the vertices v̄_{i} for 3 ≤ i ≤ n − 2 are strongly dominated by two vertices v̄_{i} and v̄_{n}, a contradicition. This is true if any v̄_{i}S. Therefore C_{n}C̄_{n} is not strong efficient when n > 3.
Conversely let n = 3. C_{3}C̄_{3} is strong efficient with three strong efficient dominating sets {v_{1}, v̄_{2}, v̄_{3}},{ v_{2}, v̄_{1}, v̄_{3}} and {v_{3}, v̄_{2}, v̄_{1}} . Therefore γ_{se}[C_{n}C̄_{n}] = 3 and #γ_{se}[CnC̄_{n}] = 3.
Theorem 2.27
K_{1,n}, K̄_{1,n}is strong efficient if and only if n = 1. Moreover$${\gamma}_{se}\left[{K}_{1,n}{\overline{K}}_{1,n}\right]=2\hspace{0.17em}\hspace{0.17em}\mathit{and}\hspace{0.17em}\#{\gamma}_{se}\left[{K}_{1,n}{\overline{K}}_{1,n}\right]=2.$$
ProofLet v, v_{i}; 1 ≤ i ≤ n be the vertices of K_{1,n}and v̄, v̄_{i}; 1 ≤ i ≤ n be the vertices of the copy of K̄_{1,n} of K̄_{1,n}. In K_{1,n}K̄_{1,n}, v is adjacet with all ${v}_{i}^{s}$ and v̄; 1 ≤ i ≤ n. ∆[K_{1,n}K̄_{1,n}] = deg(v) = n + 1, deg(v_{i}) = 2, deg(v̄_{i}) = n and deg(v̄) = 1; 1 ≤ i ≤ n. Let n > 1. Suppose K_{1,n}, K̄_{1,n} is strong efficient. Any strong efficient dominating set must contain v. Let S be a strong efficient dominating set. v strongly dominates v̄ and v_{i}; 1 ≤ i ≤ n. If v̄_{i} ∈ S, then |N_{s}[v̄_{i}] ∩ S| = | {v, v̄_{i}} | = 2 > 1. This is a contradicition. Therefore v̄_{i} ∉ S. Therefore K_{1,n}K̄_{1,n} is not strong efficient when n > 1.
Conversely let n = 1. K_{1,1}K̄_{1,1} is the path P_{4} which is obviously strong efficient with strong efficient dominating set {v, v̄_{1}} and {v̄, v_{1}}. Therefore γ_{se}[K_{1,n}K̄_{1,n}] = 2 and #γ_{se}[K_{1,n}K̄_{1,n}] = 2.