Article
KYUNGPOOK Math. J. 2019; 59(3): 363375
Published online September 23, 2019
Copyright © Kyungpook Mathematical Journal.
Some Cycle and Star Related NordhausGaddum Type Relations on Strong Eﬃcient Dominating Sets
Karthikeyan Murugan
PG and Research Department of Mathematics, The M. D. T. Hindu College and Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli627012, India
email : muruganmdt@gmail.com
Received: November 22, 2016; Revised: May 2, 2018; Accepted: June 8, 2018
Let
Keywords: strong efficient dominating sets, strong efficient domination number and number of strong efficient dominating sets.
Throughout this paper only finite, undirected and simple graphs are considered. Let
The concept of strong (weak) efficient domination in graphs was introduced by Meena et al. (see [7]). A subset
Results

1.1: γ_{se} (G ) = 1if and only if G has a full degree vertex . 
1.2: γ_{se} (K_{n} ) = 1,n ≥ 1. 
1.3: γ_{se} (K _{1,n}) = 1,n ≥ 1. 
1.4: γ_{se} (C _{3n}) =n ,n ≥ 1. 
1.5: Since C _{3n+1}and C _{3n+2}do not have efficient dominating sets, they do not have strong efficient dominating sets . 
1.6: If there exists exactly one maximum degree vertex, then any strong efficient dominating set must contain it . 
1.7 : For any path ${\gamma}_{\mathit{se}}({P}_{m})=\{\begin{array}{l}n\hspace{0.17em}if\hspace{0.17em}m=3n,n\in N,\\ n+1\hspace{0.17em}\hspace{0.17em}if\hspace{0.17em}m=3n+1,n\in N,\\ n+2\hspace{0.17em}if\hspace{0.17em}m=3n+2,n\in N.\end{array}$ 
1.8: A graph G does not admit a strong efficient dominating set if the distance between any two maximum degree vertices is exactly two . 
1.9: Any strong efficient dominating set is independent . 
1.10: The sub division graph S (G )of a graph G is obtained from G by inserting a new vertex into every edge of G . 
1.11: γ_{se} [S (C _{3}_{n} )] = 2n for all n ∈N . 
1.12: γ_{se} [S (k _{1,n})] =n + 1for all n ∈N . 
1.13 : If an efficient graph G of order n is an rregular, then $\gamma =\frac{n}{r+1}$ . 
1.14: Let G be a graph with a strong efficient dominating number γ_{se} (G ). The number of distinct strong efficient dominating sets of a graph G is denoted by #γ_{se} (G ). 
1.15: $\#{\gamma}_{se}({P}_{m})=\{\begin{array}{l}1\hspace{0.17em}if\hspace{0.17em}m=3nor\hspace{0.17em}m=3n+2,\hspace{0.17em}\hspace{0.17em}n\in N,\\ 2\hspace{0.17em}if\hspace{0.17em}m=2\hspace{0.17em}or\hspace{0.17em}m=3n+1,\hspace{0.17em}n\in N.\end{array}$ 
1.16: #γ_{se} (K_{n} ) =n ,n ∈N . 
1.17: #γ_{se} (C _{3n}) = 3,n ∈N .
In this section, line graph, jump graph, semitotal point graph, semitotal line graph, total graph, quasivertex total graph and complementary prism are defined. Cycle and start related NordhausGaddum type relations of strong efficient dominating sets and the number of strong efficient dominating sets are studied.
Definition 2.1
([12]) The
The following theorem is established first.
Theorem 2.2
Let
Therefore by Results 1.4 and 1.5,
Theorem 2.3
Now the concept of jump graph of a graph is defined.
Definition 2.4
([2]) The
Theorem 2.5
Let
Conversely suppose

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
Since
Definition 2.7
The
Theorem 2.8
Obviously
Theorem 2.9
Let

Case (i): Suppose
n = 1.PL [K _{1,1}] isP _{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 thatdeg (e_{j} ) = 1;n + 1 ≤j ≤ 2n . We see thate _{1} is adjacent with the${e}_{j}^{s}$ for 2 ≤j ≤n + 1. Hencee _{1} strongly dominates all of these vertices. Also, the verticese _{n+j} for 2 ≤j ≤n are muthually nonadjacent. Therefore {e _{1},e _{n+2},e _{n+3}, · · · ,e _{2n}} is a strong efficient dominating set ofP 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 ofP L (K _{1,n}).
Therefore
Therefore
Definition 2.10
([9]) The

(i) they are adjacent vertices of
G or 
(ii) one is a vertex of
G and the other is an edge ofG incident with it.
Theorem 2.11
Let

Case (i): Let
n = 3m + 1. ∆[T _{2}(C _{3m+1})] =deg (v_{i} ) = 4,deg (e_{i} ) = 2; 1 ≤i ≤ 3m + 1. Supposev _{1} ∈S . We have thatv _{1} strongly dominates the verticesv _{2},v _{3m+1},e _{1} ande _{3m+1}. Similarlyv _{3i−2} strongly dominatesv _{3i−3},v _{3i−1},e _{3i−3} ande _{3i−2}; 2 ≤i ≤m . Ifv _{3m} ∈S , then N_{s} [V _{3m+1}] ∩S  =  {v _{1},v _{3m}}  = 2 > 1. This is a contradicition. Thereforev _{3m} ∉S . Hence there is no vertex inS that strongly efficiently dominatesV _{3m}. HenceT _{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 anddeg (e_{i} ) = 2 for 1 ≤i ≤ 3m + 2. Supposev _{1} ∈S . The vertexv _{1} strongly dominates the verticesv _{2},v _{3m+2},e _{1} ande _{3m+2}. Similarlyv _{3i−2} strongly dominatesv _{3i−3},v _{3i−1},e _{3i−3} ande _{3i−2} for 2 ≤i ≤m . Moreover,v _{3m} andv _{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. Thereforev _{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. Thereforev _{3m+1} ∉S . Hence there is no vertex inS to strongly efficiently dominateV _{3m+1}. ThereforeT _{2}(C_{n} ) is not strong efficient whenn = 3m + 1 or 3m + 2.
Conversely suppose
Therefore
Hence
Now the following theorem is established.
Theorem 2.12
Let

Case (i): Suppose
n = 1. ThenT _{2}(K _{1,1}) is the cyclec _{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. InT _{2}(K _{1,n}),v is adjacent with all the${v}_{i}^{s}$ and${e}_{i}^{s}$ ; 1 ≤i ≤n . Thusv 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
Definition 2.13
([9]) The

(i) they are adjacent edges of
G or 
(ii) one is a vertex of
G and the other is an edge ofG incident with it.
Theorem 2.14
Theorem 2.15
Let
Suppose
Hence {
Definition 2.16
The

(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 ofG incident with it.
Theorem 2.17
Let

Case (i): Let
n = 5m +1. Supposev _{5i−4},e _{5i−2} ∈S for 1 ≤i ≤m . Thenv _{5i−4},e _{5i−2} for 1 ≤i ≤m strongly dominates all the vertices other thanv _{5m} ande _{5m}. Alsov _{5m} ande _{5m} are adjacent. Ifv _{5m} ∈S , then N_{s} [V _{5m+1}] ∩S  =  {v _{1},v _{5m}}  = 2 > 1. This is a contradicition. Thereforev _{5m} ∉S . Ife _{5m} ∈S , then N_{s} [v _{5m+1}] ∩S  =  {v _{1},e _{5m}}  = 2 > 1. This is also a contradiction. Thereforee _{5m} ∉S . This is for anyv_{i} ∈S . ThereforeT (C_{n} ) is not strong efficient whenn = 5m + 1 form ∈N . 
Case (ii): Let
n = 5m + 2. Supposev _{5i−4},e _{5i−2} ∈S for 1 ≤i ≤m . As beforev _{5i−4},e _{5i−2} for 1 ≤i ≤m strongly dominates all the vertices other thanv _{5m+1},v _{5m} ande _{5m}. Alsov _{5m+1},v _{5m} ande _{5m} are mutually adjacent. Ifv _{5m+1} ∈S , then N_{s} [V _{5m+2}] ∩S  =  {v _{1},v _{5m+1}}  = 2 > 1. This is a contradicition. Thereforev _{5m+1} ∉S . Ifv _{5m} ∈S , then N_{s} [V _{5m−1}] ∩S  =  {v _{5m},e _{5m−2}}  = 2 > 1. This is a contradicition. Thereforev _{5m} ∉S . Ife _{5m} ∈S , then N_{s} [e _{5m−1}] ∩S  =  {e _{5m},e _{5m−2}}  = 2 > 1. This is a contradicition. Thereforee _{5m} ∉S . Ife _{5m+1} ∈S , then N_{s} [e _{5m+2}] ∩S  =  {v _{1},e _{5m+1}}  = 2 > 1. This is also a contradicition. Thereforee _{5m+1} ∉S . Thereforee _{5m} ∉S . This is for anyv_{i} ∈S . ThereforeT (C_{n} ) is not strong efficient whenn = 5m + 2,m ∈N . 
Case (iii): Let
n = 5m + 3. Supposev _{5i−4},e _{5i−2} ∈S for 1 ≤i ≤m . Thenv _{5i−4},e _{5i−2} for 1 ≤i ≤m strongly dominates all the vertices other thane _{5m+2}. Ife _{5m+2} ∈S , then N_{s} [V _{5m+3}] ∩S  =  {v _{1},e _{5m+2}}  = 2 > 1. This is also a contradicition. Thereforee _{5m+2} ∉S . Thereforee _{5m} ∉S . This is for anyv_{i} ∈S . ThereforeT (C_{n} ) is not strong efficient whenn = 5m + 3,m ∈N . 
Case (iv): Let
n = 5m + 4. Supposev _{5i−4},e _{5i−2} ∈S ; 1 ≤i ≤m . As beforev _{5i−4},e _{5i−2}; 1 ≤i ≤m strongly dominates all the vertices other thanv _{5m+3},e _{5m+2} ande _{5m+3}. Ifv _{5m+3} ∈S , then N_{s} [v _{5m+4}] ∩S  =  {v _{1},v _{5m+3}}  = 2 > 1. This is a contradicition. Thereforev _{5m+3} ∉S . Ife _{5m+2} ∈S , then N_{s} [e _{5m+1}] ∩S  =  {v _{5m+1},e _{5m+2}}  = 2 > 1. This is also a contradicition. Thereforee _{5m+2} ∉S . Ife _{5m+3} ∈S , then N_{s} [v _{5m+4}] ∩S  =  {e _{5m+3},v _{1}}  = 2 > 1. This is also a contradicition. Thereforee _{5m+3} ∉S . Thereforee _{5m} ∉S . This is for anyv_{i} ∈S . ThereforeT (C_{n} ) is not strong efficient whenn = 5m + 4,m ∈N . 
Case (v): Let
n = 4. Supposev _{1} ∈S .v _{1} strongly dominatesv _{2},v _{4},e _{1} ande _{4}. Ife _{2} orv _{3} belongs toS thenv _{2} is strongly dominated by two verticesv _{1} ande _{2} orv _{1}andv _{3} respectively. Ife _{3} belongs toS thenv _{4} is strongly dominated by two verticesv _{1} ande _{3}. Thereforee _{2},e _{3} andv _{3} do not belong toS . There is no vertex inS to strongly dominate these three vertices, a contradiction. This is true if anyv_{i} ore_{i} belong toS . HenceT (C_{n} ) is not strong efficient whenn = 4. 
Case (vi): Let
n = 3. Supposev _{1} ∈S .v _{1} strongly dominates all the vertices other thane _{2}. Ife _{2} belongs toS then all the vertices other thanv _{1} are strongly dominated by two verticesv _{1} ande _{2}. Thereforee _{2} ∉S . Hence there is no vertex inS to strongly dominatee _{2}, a contradiction. This is true if anyv_{i} ore_{i} belong toS . HenceT (C_{n} ) is not strong efficient whenn = 3.
Conversely suppose
Theorem 2.18
Let

Case (i): Suppose
n = 1.T (K _{1,1}) is a cycleC _{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. InT (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
Definition 2.19
([11]) The

(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 ofG incident with it.
Theorem 2.20
Let

Case (i): Let
n = 4.∆[P (C _{4})] =deg (e_{i} ) = 4,deg (v_{i} ) = 3; 1 ≤i ≤ 4. Supposee _{1} ∈S . The vertexe _{1} strongly dominates all the vertices other thane _{3},v _{3} andv _{4}. Ife _{3} ∈S , then N_{s} [e _{2}] ∩S  =  {e _{1},e _{3}}  = 2 > 1. This is a contradicition. Thereforee _{3} ∉S . Ifv _{3} ∈S , then N_{s} [v _{1}] ∩S  =  {e _{1},v _{3}}  = 2 > 1. This is a contradicition. Thereforev _{3} ∉S . Ifv _{4} ∈S , then N_{s} [v _{2}] ∩S  =  {e _{1},v _{4}}  = 2 > 1. This is also a contradicition. Thereforev _{4} ∉S . ThereforeP (C _{4}) is not strong efficient. 
Case (ii): Let
n = 5. InP (C _{5}),deg (v_{i} ) =deg (e_{i} ) = 4 for 1 ≤i ≤ 5. Supposee _{1} ∈S . The vertexe _{1} strongly dominatesv _{2},e _{2},v _{1} ande _{5}. If eitherv _{3} ore _{3} belong toS , thene _{2} is dominated by two elementsv _{3},e _{1} ore _{3},e _{1} ofS respectively, a contradiction. Thereforev _{3} ande _{3} do not belong toS . Ifv _{4} ∈S , thenv _{2} is dominated by two elementsv _{4} ande _{1}, a contradiction. Thereforev _{4} doesnot belong toS . If eitherv _{5} ore _{4} belong toS , thene _{5} is dominated by two elementsv _{5},e _{1} ore _{4},e _{1} ofS respectively, a contradicition. Thereforev _{5} ande _{4} do not belong toS . HenceP (C _{5}) is not efficient. 
Case (iii): Let
n > 5. Then ∆[P (C_{n} )] =deg (v_{i} ) =n − 1, anddeg (e_{i} ) = 4 for 1 ≤i ≤ 4. The vertexv_{i} strongly dominates all the${v}_{j}^{s}$ other thanv _{i−1} andv _{i+1}. Alsov _{i−1} andv _{i+1} are adjacent. Ifv _{i−1} ∈S , then N_{s} [v _{i−3}] ∩S  =  {v_{i} ,v _{i−1}}  = 2 > 1. This is a contradicition. Thereforev _{i−1} ∉S . Ifv _{i+1} ∈S , then N_{s} [v _{i+3}] ∩S  =  {v_{i} ,v _{i+1}}  = 2 > 1. This is also a contradicition. Thereforev _{i+1} ∉S . ThereforeP (C_{n} ) is not strong efficient whenn > 3.
Conversely suppose
Theorem 2.21
Let
In
Conversely suppose
Definition 2.22
([11]) The

(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 ofG incident with it.
Theorem 2.23
Let

Case (i): Suppose
n = 3m ,m ∈N . We have ∆[Q (C _{3m})] =deg (v_{i} ) = 3m + 1 anddeg (e_{i} ) = 4; 1 ≤i ≤ 3m . Supposev _{1} ∈S . Thenv _{1} strongly dominates all other${v}_{j}^{s}$ ,e _{3m} ande _{1}. The remaining$\left(3m2\right){e}_{j}^{s}$ which are adjacent withv_{j} andv _{j+1} form a path of length 3m − 2. Obviouslye _{3},e _{6},e _{9}, · · · ,e _{3m−3} strongly dominates all the${e}_{j}^{s}$ excepte _{3m−1} Ife _{3m−1} ∈S then N_{s} [e _{3m}] ∩S  =  {e _{3m−1},v _{1}}  = 2 > 1. This is a contradicition. Thereforee _{3m−1} ∉S . ThereforeQ (C_{n} ) is not strong efficient whenn = 3m form ∈N . 
Case (ii): Suppose
n = 3m + 1 form ∈N . ∆[Q (C _{3m+1})] =deg (v_{i} ) = 3m + 2 anddeg (e_{i} ) = 4 for 1 ≤i ≤ 3m + 1. Supposev _{1} ∈S . Thenv _{1} strongly dominates all other${v}_{j}^{s}$ ,e _{3m+1} ande _{1}. The remaining$\left(3m1\right){e}_{j}^{s}$ which are adjacent withv_{j} andv _{j+1} form a path of length 3m − 1. Obviouslye _{3},e _{6},e _{9}, · · · ,e _{3m−3} strongly dominates all the${e}_{j}^{s}$ excepte _{3m} ande _{3m−1}. Ife _{3m} ∈S , then N_{s} [e _{3m+1}] ∩S  =  {e _{3m},v _{1}}  = 2 > 1. This is a contradicition. Thereforee _{3m} ∉S . Ife _{3m−1} ∈S , then N_{s} [e _{3m−2}]∩S  =  {e _{3m−1},e _{3m−3}}  = 2 > 1. This is also a contradicition. Thereforee _{3m−1} ∉S . ThereforeQ (C_{n} ) is not strong efficient ifn = 3m or 3m + 1,m ∈N .
Conversely suppose
Therefore
Theorem 2.24
Let
Definition 2.25
([6]) For a graph
Theorem 2.26

Case (i): Suppose
n = 4 orn = 5. The graphC _{4}C̄ _{4} andC _{5}C̄ _{5} are shown in Fig 1. The subgraph induced by the maximum degree vertices isC _{4}, which is not strong efficient. HenceC _{4}C̄ _{4} is not strong efficient.C _{5}C̄ _{5} is the Peterson graph which is not efficient. HenceC _{5}C̄ _{5} is not strong efficient. 
Case (ii): Suppose
C_{n} C̄_{n} is strong efficient. LetS be a strong efficient dominating set ofC_{n} C̄_{n} Suppose firstn > 5. Then ∆[C_{n} C̄_{n} ] =deg (v̄_{i} ) =n − 2 for 1 ≤i ≤n anddeg (v_{i} ) = 3 for 1 ≤i ≤n . Moreoverv̄ _{1} andv̄_{n} are nonadjacent. Supposev̄ _{1} ∈S and observe thatv̄ _{1} strongly dominatesv _{1} and allv̄_{i} other thanv̄ _{2} andv̄_{n} . Thereforev̄ _{2} ∈S . So N_{s} [v̄ _{4}] ∩S  =  {v̄ _{1},v̄ _{2}}  = 2 > 1. This is a contradicition. Thereforev̄ _{2} ∉S . Ifv̄_{n} ∈S , then the verticesv̄_{i} for 3 ≤i ≤n − 2 are strongly dominated by two verticesv̄_{i} andv̄_{n} , a contradicition. This is true if anyv̄_{i} S . ThereforeC_{n} C̄_{n} is not strong efficient whenn > 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
Let
Conversely let
The author is thankful to the referees for their many valuable suggestions and comments to improve the paper.
 DW. Bange, AE. Barkauskas, and PJ. Slater.
Efficient dominating sets in graphs . Application of Discrete Mathematics,, SIAM, Philadephia, 1988:189199.  G. Chartrand, H. Hevia, EB. Jarette, and M. Schultz.
Subgraph distances in graphs defined by edge transfers . Discrete Math.,170 (1997), 6379.  F. Harary. Graph theory,
, AddisonWesley, 1969.  F. Harary, TW. Haynes, and PJ. Slater.
Efficient and excess domination in graphs . J. Combin. Math. Combin. Comput.,26 (1998), 8395.  TW. Haynes, ST. Hedetniemi, and PJ. Slater. Fundamentals of domination in graphs,
, Marcel Dekker, Inc, New York, 1998.  TW. Haynes, MA. Henning, PJ. Slater, and LC. Van Der Merwe.
The complementary product of two graphs . Bull. Inst. Combin. Appl.,51 (2007), 2130.  Meena. N.
Studies in graph theoryefficient domination and related topics , Manonmaniam Sundaranar University, 2013.  K. Murugan, and N. Meena.
Some NordhausGaddum type relation on strong efficient dominating sets . J. New Results Sci.,5 (11)(2016), 416.  E. Sampathkumar, and SB. Chikkodimath.
Semitotal graphs of a graph I . J. Karnatak Univ. Sci.,18 (1973), 274280.  E. Sampathkumar, and LP. Latha.
Strong weak domination and domination balance in a graph . Discrete Math.,161 (1996), 235242.  DVSS. Sastry, and BSP. Raju.
Graph equations for line graphs, total graphs, middle graphs and quasitotal graphs . Discrete Math.,48 (1984), 113119.  H. Whitney.
Congruent graphs and the connectivity graphs . Amer. J. Math.,54 (1932), 150168.