검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

KYUNGPOOK Math. J. 2019; 59(3): 363-375

Published online September 23, 2019

Copyright © Kyungpook Mathematical Journal.

Some Cycle and Star Related Nordhaus-Gaddum Type Relations on Strong Efficient Dominating Sets

Karthikeyan Murugan

PG and Research Department of Mathematics, The M. D. T. Hindu College and Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli-627012, India
e-mail : muruganmdt@gmail.com

Received: November 22, 2016; Revised: May 2, 2018; Accepted: June 8, 2018

Let G = (V, E) be a simple graph with p vertices and q edges. A subset S of V (G) is called a strong (weak) efficient dominating set of G if for every vV (G) we have |Ns[v] ∩ S|= 1 (resp. |Nw [v] ∩ S|= 1), where Ns(v) = {uV (G) : uvE(G), deg(u) ≥ deg(v)}. The minimum cardinality of a strong (weak) efficient dominating set of G is called the strong (weak) efficient domination number of G and is denoted by γse(G) (γwe(G)). A graph G is strong efficient if there exists a strong efficient dominating set of G. In this paper, some cycle and star related Nordhaus-Gaddum type relations on strong efficient dominating sets and the number of strong efficient dominating sets are studied.

Keywords: strong efficient dominating sets, strong efficient domination number and number of strong efficient dominating sets.

roduction

Throughout this paper only finite, undirected and simple graphs are considered. Let G = (V, E) be a graph with p vertices and q edges. The degree of any vertex u in G is the number of edges incident with u and is denoted by deg(u). The minimum and maximum degree of a vertex is denoted by δ(G) and ∆(G) respectively. A vertex of degree 0 in G is called an isolated vertex and a vertex of degree 1 in G is called a pendant vertex. A subset S of V (G) is called a dominating set of G if every vertex in V (G) − S is adjacent to a vertex in S (see [5]). The domination number of a graph G, denoted by γ(G), is the minimum cardinality of a dominating set of G. Sampathkumar et al. introduced the concepts of strong and weak domination in graphs (see [10]). A subset S of V (G) is called a strong dominating set of G if for every vVS there exists a uS such that u and v are adjacent and deg(u) ≥ deg(v). A subset S of V (G) is called an efficient dominating set of G if for every vV (G), |N [v] ∩ S| = 1 (see [1] and [4]).

The concept of strong (weak) efficient domination in graphs was introduced by Meena et al. (see [7]). A subset S of V (G) is called a strong (weak) efficient dominating set of G if for every vV (G) we have |Ns[v]∩S| = 1 (resp. |Nw[v]∩S| = 1). Here, Ns(v) denotes the set of all vertices uV (G) such that uv is an edge in G and where deg(u) ≥ deg(v). The minimum cardinality of a strong (weak) efficient dominating set is called strong (weak) efficient domination number and is denoted by γse(G) (resp. γwe(G)). A graph G is strong efficient if there exists a strong efficient dominating set of G. The number of strong efficient dominating sets of a graph G is donoted by #γse(G). Murugan et al. studied the Nordhaus-Gaddum type relations on strong efficient dominating sets in [8]. In this paper, some cycle and star related Nordhaus-Gaddum type relations on strong efficient dominating sets and the number of strong efficient dominating sets are studied. For all graph theoretic terminology and notations, Harary [3] is followed. The following definitions and results are necessary for the present study.

Results

([7, 8])

  • 1.1: γse(G) = 1 if and only if G has a full degree vertex.

  • 1.2: γse(Kn) = 1, n ≥ 1.

  • 1.3: γse(K1,n) = 1, n ≥ 1.

  • 1.4: γse(C3n) = n, n ≥ 1.

  • 1.5: Since C3n+1and C3n+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γse(Pm)={nifm=3n,nN,n+1ifm=3n+1,nN,n+2ifm=3n+2,nN.

  • 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(C3n)] = 2n for all nN.

  • 1.12: γse[S(k1,n)] = n + 1 for all nN.

  • 1.13 : If an efficient graph G of order n is an r-regular, thenγ=nr+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: #γse(Pm)={1ifm=3norm=3n+2,nN,2ifm=2orm=3n+1,nN.

  • 1.16: #γse(Kn) = n, nN.

  • 1.17: #γse(C3n) = 3, nN.

In 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(Cn) is strong efficient if and only if n = 3m, mN. Furtherγse(C3m)+γse[L(C3m)]=2mand#γse(C3m)+#γse[L(C3m)]=6.

Proof

Let v1, v2, ..., vn be the vertices and ei = vivi+1; 1 ≤ in − 1, en = vnv1 be the edges of the cycle Cn. Obviously L(Cn) is a Cn with vertices e1, e2, ..., en.

Therefore by Results 1.4 and 1.5, L(Cn) is strong efficient if and only if n = 3m. Therefore γse(C3m) + γse[L(C3m)] = 2m and by Result 1.17, #γse(C3m) + #γse[L(C3m)] = 6.

Theorem 2.3

L(K1,n) is strong efficient for all n ≥ 1. Furtherγse(K1,n)+γse[L(K1,n)]=2and#γse(K1,n)+#γse[L(K1,n)]=n+1.

Proof

L(K1,n) is strong efficient for all n ≥ 1. Further γse(K1,n)+γse[L(K1,n)] = 2 and #γse(K1,n) + #γse[L(K1,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 (Cn) is strong efficient if and only if n = 3 or n = 4. Moreoverγse[J(Cn)]={3ifn=3,2ifn=4,and#γse[J(Cn)]={1ifn=3,4ifn=4.

Proof

Let v1, v2, ..., vn be vertices of Cn, and ei = vivi+1 for all 1 ≤ in − 1 and en = vnv1 be the edges. Suppose n > 4. For all i with 1 ≤ in − 1, e1i is adjacent in J (Cn) with all vertices other than ei−1 and ei+1, similarliy en is adjacent with all the vertices other than en−1 and e1. Thus J (Cn) is regular of degree n − 3. Suppose J (Cn) is strong efficient, and let S be a strong efficient dominating set of J (Cn). Suppose further that e1S. The vertex e1 strongly dominates all vertices other than e2 and en, which are adjacent. If e2S, then |Ns[e4] ∩ S| = | {e1, e2} | = 2 > 1, which is a contradicition. Therefore e2S. If enS, then |Ns[e3] ∩ S| = | {e1, en} | = 2 > 1; also a contradicition. Therefore enS. This is true for any eiS, 1 ≤ in. Hence J (Cn) is not strong efficient when n > 4.

Conversely suppose n ≤ 4. Two cases are considered.

  • Case (i): Suppose n = 3. J (C3) is 3K1 which is obviously strong efficient with the unique strong efficient dominating set {e1, e2, e3}.

  • Case (ii): Suppose n = 4. J (C4) is 2K2 for which {e1, e2},{e1, e4}, {e3, e2} and {e3, e4} are strong efficient dominating sets.

This completes the proof of the theorem.

Theorem 2.6

J (K1,n) is strong efficient for all n ≥ 1. Moreoverγse(K1,n)+γse[J(K1,n)]=n+1and#γse(K1,n)+#γse[J(K1,n)]=2.

Proof

Since J (K1,n) is n, we have γse[J (K1,n)] = n and #γse[J (K1,n)] = 1. Therefore γse(K1,n) + γse[J (K1,n)] = n + 1 and #γse(K1,n) + #γse[J (K1,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(Cn) is strong efficient if and only if n = 3m, mN . Furtherγse(C3m)+γse[PL(C3m)]=3mand#γse(C3m)+#γse[PL(C3m)]=6.

Proof

Obviously PL(Cn) is C2n and hence from Results 1.4 and 1.5,γse[P L(C3m)] = 2m and by Result 1.17, #γse[P L(C3m)] = 3. Therefore γse(C3m) + γse[PL(C3m)] = 3m and #γse(C3m) + #γse[P L(C3m)] = 6.

Theorem 2.9

PL[K1,n] is strong efficient for all n ≥ 1. Furtherγse(K1,n)+γse[PL(K1,n)]=n+1and#γse(K1,n)+#γse[PL(K1,n)]={4ifn=1,n+1ifn>1.

Proof

Let v and vi for 1 ≤ in be the vertices if K1,n and let vvi for 1 ≤ in be the edges. Let ui be the vertice obtained by subdividing the edge vvi of the star for 1 ≤ in. Let ei = vui and en+1 = uivi for 1 ≤ in be the edges of PL[K1,n].

  • Case (i): Suppose n = 1. PL[K1,1] is P2 which is obviously strong efficient and hence γse[PL(K1,1)] = 1 and #γse[PL(K1,1)] = 2.

  • Case (ii): Suppose that n > 1, that ∆P L[K1,n] = deg(ei) = n for 1 ≤ in and that deg(ej) = 1; n + 1 ≤ j ≤ 2n. We see that e1 is adjacent with the ejs for 2 ≤ jn + 1. Hence e1 strongly dominates all of these vertices. Also, the vertices en+j for 2 ≤ jn are muthually non-adjacent. Therefore {e1, en+2, en+3, · · · , e2n} is a strong efficient dominating set of P L[K1,n]. Similarly {e2, en+1, en+3, en+4, · · · , e2n}, {e3, en+1, en+2, en+4, en+5, · · · , e2n} , · · · , {en, en+1, en+2, · · · , e2n−1} is also a strong efficient dominating set of P L(K1,n).

Therefore γse[P L(K1,n)] = n and #γse(PL[K1,n])={2ifn=1,nifn>1.

Therefore γse(K1,n) + γse[P L(K1,n)] = n + 1 and #γse(K1,n)+#γse[PL(K1,n)]={4ifn=1,n+1ifn>1.

Definition 2.10

([9]) The semi-total point graph T2(G) is the graph whose vertex set is V (G) ∪ E(G) where two vertices are adjacent if and only if

  • (i) they are adjacent vertices of G or

  • (ii) one is a vertex of G and the other is an edge of G incident with it.

Theorem 2.11

T2(Cn) is strong efficient if and only if n = 3m for mN. Furtherγse(C3m)+γse[T2(C3m)]=3mand#γse(C3m)+#γse[T2(C3m)]=6.

Proof

Let v1, v2, ..., vn be the vertices and ei = vivi+1 for 1 ≤ in − 1, as well as en = vnv1 be the edges of the cycle Cn. Let n ≠ 3m. Suppose T2(Cn) is strong efficient. Let S be a strong efficient dominating set of T2(Cn).

  • Case (i): Let n = 3m + 1. ∆[T2(C3m+1)] = deg(vi) = 4, deg(ei) = 2; 1 ≤ i ≤ 3m + 1. Suppose v1S. We have that v1 strongly dominates the vertices v2, v3m+1, e1 and e3m+1. Similarly v3i−2 strongly dominates v3i−3, v3i−1, e3i−3 and e3i−2; 2 ≤ im. If v3mS, then |Ns[V3m+1] ∩ S| = | {v1, v3m} | = 2 > 1. This is a contradicition. Therefore v3mS. Hence there is no vertex in S that strongly efficiently dominates V3m. Hence T2(C3m+1) is not strong efficient.

  • Case (ii): Let n = 3m + 2, and observe that ∆[T2(C3m+2)] = deg(vi) = 4 and deg(ei) = 2 for 1 ≤ i ≤ 3m + 2. Suppose v1S. The vertex v1 strongly dominates the vertices v2, v3m+2, e1 and e3m+2. Similarly v3i−2 strongly dominates v3i−3, v3i−1, e3i−3 and e3i−2 for 2 ≤ im. Moreover, v3m and v3m+1 are adjacent.

  • Subcase (ii a): Suppose v3mS. Then |Ns[V3m−1] ∩ S| = | {v3m, v3m−2} | = 2 > 1. This is also a contradicition. Therefore v3mS.

  • Subcase (ii b): Suppose v3m+1S. Then |Ns[V3m+2] ∩ S| = | {v1, v3m+1} | = 2 > 1. This is also a contradicition. Therefore v3m+1S. Hence there is no vertex in S to strongly efficiently dominate V3m+1. Therefore T2(Cn) is not strong efficient when n = 3m + 1 or 3m + 2.

Conversely suppose n = 3m. Then ∆[T2(C3m)] = deg(vi) = 4 and deg(ei) = 2 for 1 ≤ i ≤ 3m. Also, eis are non-adjacent. For 1 ≤ im the vertex v3i−2 strongly dominate all the vertices other than e3i−1. The vertices e3i−1 for 1 ≤ im are strongly dominated by themselves. Hence {v3i−2, e3i−1; 1 ≤ im} is a strong efficient dominating set of T2(C3m). By symmetry, {v3i−1, e3i; 1 ≤ im} and {v3i, e3i−2; 1 ≤ im} are also strong efficient dominating sets of T2(Cn).

Therefore γse[T2(C3m)] = 2m and #γse[T2(C3m)] = 3.

Hence γse(C3m) + γse[T2(C3m)] = 3m and #γse(C3m) + #γse[T2(C3m)] = 6

Now the following theorem is established.

Theorem 2.12

T2(K1,n) is strong efficient for all n ≥ 1. Furtherγse(K1,n)+γse[T2(K1,n)]=2and#γse(K1,n)+#γse[T2(K1,n)]={5ifn=1,2ifn>1.

Proof

Let v and vi for 1 ≤ in be the vertices and ei = vvi for 1 ≤ in be the edges of the star K1,n.

  • Case (i): Suppose n = 1. Then T2(K1,1) is the cycle c3 for which {e1}, {v}, {v1} are the strong efficient dominating sets. Hence γse[T2(K1,1)] = 1 and #γse[T2(K1,1)] = 3.

  • Case (ii): Suppose n > 1. In T2(K1,n), v is adjacent with all the vis and eis; 1 ≤ in. Thus v is the unique full degree vertex. Therefore, by Result 1.1, γse[T2(K1,n)] = 1 and #γse[T2(K1,n)] = 1.

Therefore γse(K1,n) + γse[T2(K1,n)] = 2 and #γse(K1,n)+#γse[T2(K1,n)]={5ifn=1,2ifn>1.

Definition 2.13

([9]) The semi-total line graph T1(G) is the graph whose vertex set is V (G) ∪ E(G) where two vertices are adjacent if and only if

  • (i) they are adjacent edges of G or

  • (ii) one is a vertex of G and the other is an edge of G incident with it.

Theorem 2.14

T1(Cn) is strong efficient if and only if n = 3m, mN . Furtherγse(C3m)+γse[T1(C3m)]=3mand#γse(C3m)+#γse[T1(C3m)]=6.

Proof

T1(Cn) is obtained from T2(Cn) by replacing vi and ei. Hence the result follows from Theorem 2.11.

Theorem 2.15

T1(K1,n) is strong efficient for all n ≥ 1. Furtherγse(K1,n)+γse[T1(K1,n)]=n+1,ifn1and#γse(K1,n)+#γse[T1(K1,n)]={3ifn=1,n+1ifn>1.

Proof

Let v and vi for 1 ≤ in be the vertices and ei = vvi for 1 ≤ in be the edges of the star K1,n.

T1(K1,1) is P3 which is strong efficient and γse[T1(K1,1)] = 1. Thus #γse(K1,n) + #γse[T1(K1,n)] = 3

Suppose n ≥ 2. In T1(K1,n), we have deg(v) = n, deg(v)i = 1, and deg(ei) = n + 1 = ∆[T1(K1,n)] for 1 ≤ in. Each ei strongly uniquely dominates v and all vj’s for ji.

Hence {ei, vj|ji, 1 ≤ jn} for 1 ≤ in, form strong efficient dominating sets of T1(K1,n). Therefore T1(K1,n) is strong efficient and γse(K1,n) = n, if n ≥ 1. #γse[T1(K1,n)] = n. Hence #γse(K1,n) + #γse[T1(K1,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 (Cn) is strong efficient if and only if n = 5m, mN. Furtherγse[T(C5m)]=2mand#γse[T(C5m)]=5.

Proof

Let v1, v2, . . . , vn be the vertices and ei = vivi+1 for 1 ≤ in − 1 and en = vnv1 be the edges of the cycle Cn. In T (Cn), vi is adjacent with vi+1, vi−1, ei and ei−1 for 2 ≤ in − 1. We have that ei is adjacent with ei−1, ei+1, vi and vi+1 for 2 ≤ in − 1, and that v1 is adjacent with v2, vn, e1 and en. The vertex vn is adjacent with vn−1, v1, en−1 and en. The vertex e1 is adjacent with e2, en, v1 and v2. The vertex en is adjacent with vn, v1, en−1 and e1. Hence deg(vi) = deg(ei) = 4 for 1 ≤ in. Therefore T (Cn) is regular of degree 4. Suppose n ≠ 5m. Suppose T (Cn) is strong efficient. Let S be a strong efficient dominating set.

  • Case (i): Let n = 5m+1. Suppose v5i−4, e5i−2S for 1 ≤ im. Then v5i−4, e5i−2 for 1 ≤ im strongly dominates all the vertices other than v5m and e5m. Also v5m and e5m are adjacent. If v5mS, then |Ns[V5m+1] ∩ S| = | {v1, v5m} | = 2 > 1. This is a contradicition. Therefore v5mS. If e5mS, then |Ns[v5m+1] ∩ S| = | {v1, e5m} | = 2 > 1. This is also a contradiction. Therefore e5mS. This is for any viS. Therefore T (Cn) is not strong efficient when n = 5m + 1 for mN.

  • Case (ii): Let n = 5m + 2. Suppose v5i−4, e5i−2S for 1 ≤ im. As before v5i−4, e5i−2 for 1 ≤ im strongly dominates all the vertices other than v5m+1, v5m and e5m. Also v5m+1, v5m and e5m are mutually adjacent. If v5m+1S, then |Ns[V5m+2] ∩ S| = | {v1, v5m+1} | = 2 > 1. This is a contradicition. Therefore v5m+1S. If v5mS, then |Ns[V5m−1] ∩ S| = | {v5m, e5m−2} | = 2 > 1. This is a contradicition. Therefore v5mS. If e5mS, then |Ns[e5m−1] ∩ S| = | {e5m, e5m−2} | = 2 > 1. This is a contradicition. Therefore e5mS. If e5m+1S, then |Ns[e5m+2] ∩ S| = | {v1, e5m+1} | = 2 > 1. This is also a contradicition. Therefore e5m+1S. Therefore e5mS. This is for any viS. Therefore T (Cn) is not strong efficient when n = 5m + 2, mN .

  • Case (iii): Let n = 5m + 3. Suppose v5i−4, e5i−2S for 1 ≤ im. Then v5i−4, e5i−2 for 1 ≤ im strongly dominates all the vertices other than e5m+2. If e5m+2S, then |Ns[V5m+3] ∩ S| = | {v1, e5m+2} | = 2 > 1. This is also a contradicition. Therefore e5m+2S. Therefore e5mS. This is for any viS. Therefore T (Cn) is not strong efficient when n = 5m + 3, mN .

  • Case (iv): Let n = 5m + 4. Suppose v5i−4, e5i−2S; 1 ≤ im. As before v5i−4, e5i−2; 1 ≤ im strongly dominates all the vertices other than v5m+3, e5m+2 and e5m+3. If v5m+3S, then |Ns[v5m+4] ∩ S| = | {v1, v5m+3} | = 2 > 1. This is a contradicition. Therefore v5m+3S. If e5m+2S, then |Ns[e5m+1] ∩ S| = | {v5m+1, e5m+2} | = 2 > 1. This is also a contradicition. Therefore e5m+2S. If e5m+3S, then |Ns[v5m+4] ∩ S| = | {e5m+3, v1} | = 2 > 1. This is also a contradicition. Therefore e5m+3S. Therefore e5mS. This is for any viS. Therefore T (Cn) is not strong efficient when n = 5m + 4, mN .

  • Case (v): Let n = 4. Suppose v1S. v1 strongly dominates v2, v4, e1 and e4. If e2 or v3 belongs to S then v2 is strongly dominated by two vertices v1 and e2 or v1and v3 respectively. If e3 belongs to S then v4 is strongly dominated by two vertices v1 and e3. Therefore e2, e3 and v3 do not belong to S. There is no vertex in S to strongly dominate these three vertices, a contradiction. This is true if any vi or ei belong to S. Hence T (Cn) is not strong efficient when n = 4.

  • Case (vi): Let n = 3. Suppose v1S. v1 strongly dominates all the vertices other than e2. If e2 belongs to S then all the vertices other than v1 are strongly dominated by two vertices v1 and e2. Therefore e2S. Hence there is no vertex in S to strongly dominate e2, a contradiction. This is true if any vi or ei belong to S. Hence T (Cn) is not strong efficient when n = 3.

Conversely suppose n = 5m. In T (C5m), v5i−4 strongly dominates the vertices v5i−3, e5i−4, e5m and v5i−1; 1 ≤ im. Similarly e5i−2 strongly dominates the vertices e5i−3, e5i−1, v5i−2 and v5i−1; 1 ≤ im. Hence {v5i−4, e5i+2; 1 ≤ im} are also strong efficient dominating sets of T (C5m). Therefore γse[T (C5m)] = 2m and #γse[T (C5m)] = 5, mN .

Theorem 2.18

T (K1,n) is strong efficient for all n ≥ 1. Furtherγse(K1,n)+γse[T(K1,n)]=2and#γse(K1,n)+#γse[T(K1,n)]={5ifn=1,2ifn>1.

Proof

Let v and vi for 1 ≤ in be the vertices and ei = vvi be the edges of the star K1,n.

  • Case (i): Suppose n = 1. T (K1,1) is a cycle C3 for which {e1}, {v}, {v1} are the strong efficient dominating set.

    Hence γse[T (K1,1)] = 1 and #γse[T (K1,1)] = 3.

  • Case (ii): Suppose n > 1. In T (K1,n), v is adjacent with all vis and eis for 1 ≤ in.

    Hence v is the unique full degree vertex, deg(vi) = 2, deg(ei) = 1 + i for 1 ≤ in.

    By Result 1.1, γse[T (K1,n)] = 1 and #γse[T (K1,n)] = 1.

Therefore γse(K1,n) + γse[T (K1,n)] = 2 and #γse(K1,n)+#γse[T(K1,n)]={5ifn=1,2ifn>1.

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 (Cn) is strong efficient if and only if n = 3. Furtherγse[P(Cn)]=2and#γse[P(Cn)]=3.

Proof

Let v1, v2, ..., vn be the vertices and ei= vivi+1 for 1 ≤ in − 1, en= vnv1 be the edges of the cycle Cn. Let n > 3. Suppose P (Cn) is strong efficient. Let S be a strong efficient dominating set of P (Cn).

  • Case (i): Let n = 4.∆[P (C4)] = deg(ei) = 4, deg(vi) = 3; 1 ≤ i ≤ 4. Suppose e1S. The vertex e1 strongly dominates all the vertices other than e3, v3 and v4. If e3S, then |Ns[e2] ∩ S| = | {e1, e3} | = 2 > 1. This is a contradicition. Therefore e3S. If v3S, then |Ns[v1] ∩ S| = | {e1, v3} | = 2 > 1. This is a contradicition. Therefore v3S. If v4S, then |Ns[v2] ∩ S| = | {e1, v4} | = 2 > 1. This is also a contradicition. Therefore v4S. Therefore P (C4) is not strong efficient.

  • Case (ii): Let n = 5. In P (C5), deg(vi) = deg(ei) = 4 for 1 ≤ i ≤ 5. Suppose e1S. The vertex e1 strongly dominates v2, e2, v1 and e5. If either v3 or e3 belong to S, then e2 is dominated by two elements v3, e1 or e3, e1 of S respectively, a contradiction. Therefore v3 and e3 do not belong to S. If v4S, then v2 is dominated by two elements v4 and e1, a contradiction. Therefore v4 doesnot belong to S. If either v5 or e4 belong to S, then e5 is dominated by two elements v5, e1 or e4, e1 of S respectively, a contradicition. Therefore v5 and e4 do not belong to S. Hence P (C5) is not efficient.

  • Case (iii): Let n > 5. Then ∆[P (Cn)] = deg(vi) = n − 1, and deg(ei) = 4 for 1 ≤ i ≤ 4. The vertex vi strongly dominates all the vjs other than vi−1 and vi+1. Also vi−1 and vi+1 are adjacent. If vi−1S, then |Ns[vi−3] ∩ S| = | {vi, vi−1} | = 2 > 1. This is a contradicition. Therefore vi−1S. If vi+1S, then |Ns[vi+3] ∩ S| = | {vi, vi+1} | = 2 > 1. This is also a contradicition. Therefore vi+1S. Therefore P (Cn) is not strong efficient when n > 3.

Conversely suppose n = 3. Obviously {e1, v3} , {e2, v1} and {e1, v3} are strong efficient dominating sets P (C3). Therefore γse[P (C3)] = 2 and #γse[P (C3)] = 3.

Theorem 2.21

P (K1,n) is strong efficient if and only if n = 1. Furtherγse[P(K1,1)]=#γse[P(K1,n)]=1.

Proof

Let v, v1, v2, ..., vn be the vertices and ei = vvi for 1 ≤ in be the edges of the star K1,n. Suppose n > 1. Let P (K1,n) be strong efficient and let S be a strong efficient dominating set of P (K1,n).

In P (K1,n) the vertex vi is adjacent with all other vjs and ei for 1 ≤ in. Therefore deg(vi) = n. Also ei is adjacent with all other ejs, vi and v for 1 ≤ in. Therefore deg(ei) = n + 1. Similarily v is adjacent with all other ejs for 1 ≤ in. Therefore deg(v) = n. Suppose eiS. Then ei strongly dominates all other ejs, vi and v; 1 ≤ in. Suppose vjS, ji, then |Ns[vi] ∩ S| = | {ei, vj} | = 2 > 1. This is a contradicition. Therefore vjS. Therefore P (K1,n) is not strong efficient if n > 1.

Conversely suppose n = 1. Then P (K1,1) is P3 which is obviously strong efficient with the unique strong efficient dominating set {e1}. Therefore γse[P (K1,1)] = #γse[P (K1,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(Cn) is strong efficient if and only if n = 3m + 2, mN. Furtherγse[Q(C3m+2)]=m+1and#γse[Q(C3m+2)]=3m+2.

Proof

Let v1, v2, ..., vn be the vertices and ei = vivi+1 for 1 ≤ in − 1, en = vnv1 be the edges of the cycle Cn. Let n ≠ 3m + 2, mN . Suppose Q(Cn) is strong efficient. Let S be a strong efficient dominating set of Q(Cn).

  • Case (i): Suppose n = 3m, mN . We have ∆[Q(C3m)] = deg(vi) = 3m + 1 and deg(ei) = 4; 1 ≤ i ≤ 3m. Suppose v1S. Then v1 strongly dominates all other vjs, e3m and e1. The remaining (3m2)ejs which are adjacent with vj and vj+1 form a path of length 3m − 2. Obviously e3, e6, e9, · · · , e3m−3 strongly dominates all the ejs except e3m−1 If e3m−1Sthen |Ns[e3m] ∩ S| = | {e3m−1, v1} | = 2 > 1. This is a contradicition. Therefore e3m−1S. Therefore Q(Cn) is not strong efficient when n = 3m for mN .

  • Case (ii): Suppose n = 3m + 1 for mN. ∆[Q(C3m+1)] = deg(vi) = 3m + 2 and deg(ei) = 4 for 1 ≤ i ≤ 3m + 1. Suppose v1S. Then v1 strongly dominates all other vjs, e3m+1 and e1. The remaining (3m1)ejs which are adjacent with vj and vj+1 form a path of length 3m − 1. Obviously e3, e6, e9, · · · , e3m−3 strongly dominates all the ejs except e3m and e3m−1. If e3mS, then |Ns[e3m+1] ∩ S| = | {e3m, v1} | = 2 > 1. This is a contradicition. Therefore e3mS. If e3m−1S, then |Ns[e3m−2]∩S| = | {e3m−1, e3m−3} | = 2 > 1. This is also a contradicition. Therefore e3m−1S. Therefore Q(Cn) is not strong efficient if n = 3m or 3m + 1, mN .

Conversely suppose n = 3m + 2 for mN . Then ∆[Q(C3m+2)] = deg(vi) = 3m + 3 and deg(ei) = 4 for 1 ≤ i ≤ 3m + 2. Suppose v1S. We see that v1 strongly dominates all other vjs, e3m+2 and e1. The remaining 3m vertices ejs which are adjacent with vj and vj+1 form a path of length 3m. Obviously e3, e6, e9, · · · , e3m strongly dominates all the remaining ejs. Hence {v1, e3, e6, e9, · · · , e3m} is a strong efficient dominating set. Similarly {v2, e4, e7, e10, · · · , e3m+1},{v3, e5, e8, e10, · · · , e3m+2}{v4, e6, e9, e12, · · · , e3m, e1},{v5, e7, e10, e13, · · · , e3m+1, e2} · · · and {v3m+2, e2, e5, e8 , · · · , e3m−1} are also strong efficient dominating sets.

Therefore γse[Q(C3m+2)] = m + 1 and #γse[Q(C3m+2)] = 3m + 2, mN .

Theorem 2.24

Q(K1,n) is strong efficient for all n ≥ 1. Furtherγse(K1,n)+γse[Q(K1,n)]=2and#γse(K1,n)+#γse[Q(K1,n)]={5ifn1,2ifn>1.

Proof

Let v and vi for 1 ≤ in be the vertices and ei= vvi be the edges of the star K1,n. If n = 1, then Q(K1,1) is a cycle C3. So γse[Q(K1,1)] = 1 and #γse[Q(K1,1)] = 3. So let n > 1. In Q(K1,n), v is adjacent with all vis and eis for 1 ≤ in. Then v is the unique full degree vertex. Therefore by Result 1.1, γse[Q(K1,n)] = 1 and #γse[Q(K1,n)] = 1. Therefore γse(K1,n) + γse[Q(K1,n)] = 2 and #γse(K1,n)+#γse[Q(K1,n)]={5ifn=1,2ifn>1.

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

Cnnis strong efficient if and only if n = 3. Moreover γse[Cnn] = 3 and #γse[Cnn] = 3.

Proof

Let v1, v2, ..., vnbe the vertices of the cycle Cnand v̄1, 2, · · ·, nbe the vertices in the copy of C̄n. Let n > 3.

  • Case (i): Suppose n = 4 or n = 5. The graph C44 and C55 are shown in Fig 1. The subgraph induced by the maximum degree vertices is C4, which is not strong efficient. Hence C44 is not strong efficient. C55 is the Peterson graph which is not efficient. Hence C55 is not strong efficient.

  • Case (ii): Suppose Cnn is strong efficient. Let S be a strong efficient dominating set of Cnn Suppose first n > 5. Then ∆[Cnn] = deg(i) = n − 2 for 1 ≤ in and deg(vi) = 3 for 1 ≤ in. Moreover 1 and n are non-adjacent. Suppose 1S and observe that 1 strongly dominates v1 and all i other than 2 and n. Therefore 2S. So |Ns[4] ∩ S| = | {1, 2} | = 2 > 1. This is a contradicition. Therefore 2S. If nS, then the vertices i for 3 ≤ in − 2 are strongly dominated by two vertices i and n, a contradicition. This is true if any iS. Therefore Cnn is not strong efficient when n > 3.

    Conversely let n = 3. C33 is strong efficient with three strong efficient dominating sets {v1, 2, 3},{ v2, 1, 3} and {v3, 2, 1} . Therefore γse[Cnn] = 3 and #γse[CnC̄n] = 3.

Theorem 2.27

K1,n, 1,nis strong efficient if and only if n = 1. Moreoverγse[K1,nK¯1,n]=2and#γse[K1,nK¯1,n]=2.

Proof

Let v, vi; 1 ≤ in be the vertices of K1,nand , i; 1 ≤ in be the vertices of the copy of 1,n of 1,n. In K1,n1,n, v is adjacet with all vis and ; 1 ≤ in. ∆[K1,n1,n] = deg(v) = n + 1, deg(vi) = 2, deg(i) = n and deg() = 1; 1 ≤ in. Let n > 1. Suppose K1,n, 1,n is strong efficient. Any strong efficient dominating set must contain v. Let S be a strong efficient dominating set. v strongly dominates and vi; 1 ≤ in. If iS, then |Ns[i] ∩ S| = | {v, i} | = 2 > 1. This is a contradicition. Therefore iS. Therefore K1,n1,n is not strong efficient when n > 1.

Conversely let n = 1. K1,11,1 is the path P4 which is obviously strong efficient with strong efficient dominating set {v, 1} and {, v1}. Therefore γse[K1,n1,n] = 2 and #γse[K1,n1,n] = 2.

The author is thankful to the referees for their many valuable suggestions and comments to improve the paper.

  1. DW. Bange, AE. Barkauskas, and PJ. Slater. Efficient dominating sets in graphs. Application of Discrete Mathematics, , SIAM, Philadephia, 1988:189-199.
  2. G. Chartrand, H. Hevia, EB. Jarette, and M. Schultz. Subgraph distances in graphs defined by edge transfers. Discrete Math., 170(1997), 63-79.
    CrossRef
  3. F. Harary. Graph theory, , Addison-Wesley, 1969.
    CrossRef
  4. F. Harary, TW. Haynes, and PJ. Slater. Efficient and excess domination in graphs. J. Combin. Math. Combin. Comput., 26(1998), 83-95.
  5. TW. Haynes, ST. Hedetniemi, and PJ. Slater. Fundamentals of domination in graphs, , Marcel Dekker, Inc, New York, 1998.
  6. TW. Haynes, MA. Henning, PJ. Slater, and LC. Van Der Merwe. The complementary product of two graphs. Bull. Inst. Combin. Appl., 51(2007), 21-30.
  7. Meena. N. Studies in graph theory-efficient domination and related topics, Manonmaniam Sundaranar University, 2013.
  8. K. Murugan, and N. Meena. Some Nordhaus-Gaddum type relation on strong efficient dominating sets. J. New Results Sci., 5(11)(2016), 4-16.
  9. E. Sampathkumar, and SB. Chikkodimath. Semi-total graphs of a graph I. J. Karnatak Univ. Sci., 18(1973), 274-280.
  10. E. Sampathkumar, and LP. Latha. Strong weak domination and domination balance in a graph. Discrete Math., 161(1996), 235-242.
    CrossRef
  11. DVSS. Sastry, and BSP. Raju. Graph equations for line graphs, total graphs, middle graphs and quasitotal graphs. Discrete Math., 48(1984), 113-119.
    CrossRef
  12. H. Whitney. Congruent graphs and the connectivity graphs. Amer. J. Math., 54(1932), 150-168.
    CrossRef