1,519
Views
3
CrossRef citations to date
0
Altmetric
Research Article

Double domination in signed graphs

& | (Reviewing Editor)
Article: 1186135 | Received 06 Mar 2016, Accepted 21 Apr 2016, Published online: 25 Jul 2016

Abstract

A graph with either positive or negative labels on the edge becomes a signed graph. Given a signed graph Σ=(V,E,σ), a subset D of V is said to be a double dominating set for Σ, if it satisfies the following conditions: (i) every vertex u of Σ is either in D and u has at least one neighbour in D or whenever uV\D, |N(u)D|2 (ii) Σ[D:V\D] is balanced where N(u) denotes the open neighbourhood of a vertex u and Σ[D:V\D] is the subgraph of the Σ induced by the edges between the vertices in D and V\D. In this paper, we initiate the discussion on the double domination in signed graphs.

Mathematics subject classifications:

Public Interest Statement

Domination in graphs is one of the major research areas in graph theory. Currently, many interesting and important researches are taking place in this area. Double domination is a particular type of domination and the double domination in graphs is relative new research area and hence there is a wide scope for studies in this particular area of domination theory. Well-known mathematicians F. Harary and T. Haynes initiated the studies in the double domination in graph theory. Later, B. D. Acharya extended the domination theory to different types of signed graphs. Being a relatively new research area, double domination in graphs offers much further investigations. Domination theory has proved to have many applications in many theoretical as well as practical real-life problems like optimization problems, communication problems, network problems, etc.

1. Introduction

Graphs used in this article, unless otherwise mentioned, will be undirected, simple and finite. For all definitions in (unsigned) graph theory, one can refer to Harary (Citation1972) and for the terminology and definitions in the theory of dominations for simple graphs, we refer the reader to Chartrand and Zang (Citation2009), Haynes, Hedetneimi, and Slater (Citation1998a,Citation1998b). Signed graphs (also called sigraphs) are graphs with positive or negative labels on the edges. Formally, a signed graph is an ordered pair Σ=(G,σ) where G=(V,E) is a graph called the underlying graph of Σ and σ:E{+1,-1} called a signing, is a function (also called a signature) from the edge set E of G into the set {+1,-1}. For more details on theory and applications of signed graphs, one may refer to Germina and Shahul Hameed (Citation2010), Germina, Shahul Hameed, and Zaslavsky (Citation2011), Harary (Citation1953), Zaslavsky (Citation1982, Citation1998).

A signed graph is all-positive (respectively, all-negative) if all of its edges are positive (negative); further, it is said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. +G denotes an all-positive graph and +Kn an all-positive complete graph. Similarly, -Kn represents an all-negative complete graph. Note that a graph can be considered to be a homogeneous signed graph. A signed graph Σ is said to be balanced or cycle balanced if all of its cycles are positive, where the sign of a cycle is the product of the signs of its edges. We use N(u) to denote the open neighbourhood of a vertex u in a graph.

We denote by Pn(r), where 0rn-1, signed paths of order n and size n-1 with r negative edges . Also Cn(r), for 0rn, denotes signed cycles with r negative edges. If ζ:V{+1,-1} is a function , called a switching function, then switching of the signed graph Σ=(G,σ) by ζ means changing σ to σζ defined by(1) σζ(uv)=ζ(u)σ(uv)ζ(v).(1)

The switched graph, denoted by Σζ, is the signed graph Σζ=(G,σζ). We call two signed graphs Σ1=(G,σ1) and Σ2=(G,σ2)switching equivalent, if there exists a switching function ζ:V{+1,-1} such that Σ1=Σ2ζ.

The following important result will be used very often in signed graph theory.

Lemma 1.1

(Zaslavsky, Citation1982)    A signed graph is balanced if and only if it can be switched to an all-positive signed graph.

2. Double domination in signed graphs

Domination theory for unsigned graphs is a well-developed area of knowledge with plenty of real-life applications where the hectic research is still on, a survey of which can be found in Haynes et al. (Citation1998a,Citation1998b). Acharya (Citation2013) initiated the discussion of domination theory for signed graphs by giving the following definition.

Definition 2.1

(Acharya, Citation2013)    Let Σ=(V,E,σ) be a signed graph. A subset DV of vertices of Σ is a dominating set of Σ, if there exists a marking μ:V{+1,-1} of Σ such that every vertex u of Σ is either in D or whenever uV\D, N(u)D and σ(uv)=μ(u)μ(v) for every vN(u)D.

Ashraf and Germina (Citation2015) gave a simple characterization of dominating sets of a signed graph in terms of balance as follows.

We use Σ[D:V\D] to denote the subgraph of a signed graph Σ induced by the edges between D and V\D when DV.

Theorem 2.2

(Ashraf & Germina, Citation2015)    If D is a dominating set of G, then it is a dominating set for the signed graph Σ=(G,σ) if and only if Σ[D:V\D] is balanced.

Double domination theory for unsigned graph, initiated by Harary and Haynes in their seminal paper (Citation2000), is now a hot area of research in graph theory. Based on the characterization in Theorem 2.2, we now define the double domination in signed graph as follows.

Definition 2.3

Let Σ=(G,σ) be a signed graph where G=(V,E). A subset DV of vertices of Σ is a double dominating set of Σ, if it satisfies the following conditions: (i) every vertex u of Σ is either in D and u has at least one neighbour in D or whenever uV\D, |N(u)D|2 (ii)Σ[D:V\D] is balanced.

A dominating set (respectively, a double dominating set) D of Σ is called a minimal dominating set (respectively, a double dominating set) if no proper subset of D becomes a dominating set (respectively, a double dominating set). A minimum dominating set is a minimal dominating set with least cardinality. This least number is called domination number of Σ and is denoted by γ(Σ) . We use γ×2(Σ) to denote the double domination number of Σ.

Now we exhibit some of the major distinctions between the double domination in unsigned graphs and that of signed graphs. In the case of unsigned graphs, if S is a double dominating set for G, then S\{x} dominates G which is not true in the case of signed graphs. To see this, we have provided an example in Figure .

Figure 1. D\{x} not dominates Σ.

Figure 1. D\{x} not dominates Σ.

Also, if D1 and D2 are disjoint dominating sets for the unsigned graph G with no isolated vertices, then it is given in Harary and Haynes (Citation2000) that their union D1D2 will be a double dominating set for G. But the failure of this result in the case of signed graphs is illustrated in Figure . See that the sets D1={v1} and D2={v3} are disjoint dominating sets. But their union is not a double dominating set for Σ.

Figure 2. D1D2 is not a dominating set for Σ.

Figure 2. D1∪D2 is not a dominating set for Σ.

One more interesting distinction is that vertices of maximal independent set of edges in the case of unsigned graphs do form a double dominating set for it. But this result also fails in the case of signed graphs as given in Figure . Here, M={e2,e5} is a maximal independent set. But the set of end vertices of these edges, namely, {v2,v3,v5,v6} is not a double dominating set.

Figure 3. M={e2,e5} is a maximal independent set, but {v2,v3,v5,v6} is not a double dominating set.

Figure 3. M={e2,e5} is a maximal independent set, but {v2,v3,v5,v6} is not a double dominating set.

Moreover, in the case of unsigned graphs, super sets of a double dominating set will be again a double dominating set. But this fails for signed graphs for which the following Figure is a counter example.

Figure 4. D={v5,v6,v7} is a dominating set; but D{v3}={v3,v5,v6,v7} is not

Figure 4. D={v5,v6,v7} is a dominating set; but D∪{v3}={v3,v5,v6,v7} is not

More details on the domination theory for signed graphs can be found in Ashraf and Germina (Citation2015) , Germina and Ashraf (Citation2013), Ashraf and Germina (Citation2014). Before we proceed, we note that the following is an important result in Acharya (Citation2013) which will be used in the sequel.

Theorem 2.4

(Acharya, Citation2013)    Domination is invariant under switching.

It is worthy to note that every double dominating set is a dominating set. That is, if we denote the set of all double dominating sets for a signed graph Σ by DΣ×2 and set of all dominating sets by DΣ, then(2) DΣ×2DΣ.(2)

In light of Equation 2, it is evident that(3) γ×2(Σ)γ(Σ).(3)

The inequality in Equation 3 is strict. To see this, take the case of signed cycle C4(1) where γ(C4(1))=2 and γ×2(C4(1))=3. Now we provide a list of important observations regarding double domination of signed graphs.

Observation 2.5

Any double dominating set for a signed graph should include all its end vertices and their neighbours.

Observation 2.6

Double domination is not possible in the case of a signed graph with isolated vertices.

Theorem 2.7

Double domination is invariant under switching.

Proof

Let D be a double dominating set for the signed graph Σ which is switched to Σζ. Σ[D:V\D] is balanced. Subgraphs of switching equivalent graphs being switching equivalent, Σζ[D:V\D] is balanced. Hence, D is a double dominating set for Σζ. Converse follows from the fact that (Σζ)ζ=Σ.

Corollary 2.8

γ×2(Σ)=γ×2(Σζ)

Proof

Proof follows from Theorem 2.7.

In Germina and Ashraf (Citation2013), it is defined that a set DV is an open dominating set (also called total dominating set) of the signed graph Σ=(V,E,σ), if every vertex of Σ is adjacent to at least one vertex of D and if there exists a marking μ:V{+1,-1} such that σ(uv)=μ(u)μ(v) for every adjacent uD and vV\D. Also the minimum cardinality of an open dominating set is defined as the open domination number of Σ denoted by γt(Σ). An open dominating set of cardinality γt(Σ) is a minimum open dominating set for Σ. More details on the open domination for signed graphs can be had from Germina and Ashraf (Citation2013).

Observation 2.9

Every double dominating set is an open dominating set.

Thus, we have(4) γt(Σ)γ×2(Σ).(4)

To see if the inequality in (Equation 4) can become strict, we provide the following example. Consider the signed graph Σ built on the underlying graph in Figure where γt(Σ)=4 and γ×2(Σ)=8.

Figure 5. Helm graph H4.

Figure 5. Helm graph H4.

The second value is computed based on the observation made above that all end vertices and their neighbours belong to the double dominating set. To illustrate the case when the two become equal, consider the signed graph Σ in Figure built on the complete graph K5 where γt(Σ)=γ×2(Σ)=4.

Figure 6. A signed K5. Note: Dashes denote the negative edges.

Figure 6. A signed K5. Note: Dashes denote the negative edges.

Note that every double dominating set for the signed graph is a double dominating set for its underlying graph, but not conversely. This is illustrated in Figure where {v1,v2} is a double dominating set for G but not for Σ.

Figure 7. The set {v1,v2} is a double dominating set for G but not for Σ.

Figure 7. The set {v1,v2} is a double dominating set for G but not for Σ.

Thus, in general,(5) γ×2(G)γ×2(Σ).(5)

when Σ=(V,E,σ) is a signed graph and DV is a minimum double dominating set for the underlying graph G=(V,E) and Σ[D:V\D] is balanced, then(6) γ×2(G)=γ×2(Σ).(6)

Using Equation (6), the following identities are obtained: the double domination in the case of corresponding underlying graphs are taken from Blidia, Chellali, Haynes, and Henning (Citation2006) and Harary and Haynes (Citation2000).

(i)

In the case of signed Petersen graph Σ, γ×2(Σ)=6.

(ii)

In the case of signed cycle γ×2(Cn(r))=2n3.

(iii)

In the case of signed paths, γ×2(Pn(r))=2n3+1 if n0(mod3) and γ×2(Pn(r))=2n3, otherwise.

Now before we proceed, the following definitions and a theorem from Ashraf and Germina (Citation2015) are to be mentioned.

Definition 2.10

(Ashraf & Germina, Citation2015)    Let SV of a signed graph Σ and uS. The private neighbourhood of u relative to S in Σ, denoted by PN(u,S) is the set of vertices which is in the closed neighbourhood of u but not in the closed neighbourhood of any vertex in S\{u}. That is,PN(u,S)=N[u]\(vS\{u}N[v])

Note that uPN(u,S) if and only if u is an isolated vertex of Σ[S] in Σ. A vertex vPN(u,S) is called a private neighbour of u with respect to S.

Definition 2.11

(Ashraf & Germina, Citation2015)    An SV is called an irredundant set if PN(u,S) for every uS.

In this regard, the following theorem found in Ashraf and Germina (Citation2015) is significant.

Theorem 2.12

(Ashraf & Germina, Citation2015)    If D is a minimum dominating set for Σ=(G,σ), then it is irredundant.

But, in the case of double domination of signed graphs, we have

Observation 2.13

If D is a minimum double dominating set for Σ, then it need not be irredundant. For example, the signed graph built on Petersen graph given in Figure , D={v1,v4,v5,v6,v8,v9} is a minimum double dominating set but it is not irredundant since PN(v5,D)=.

Figure 8. Petersen graph.

Figure 8. Petersen graph.

3. Double domination number

Theorem 3.1

Every signed graph with no isolated vertices has a double dominating set and hence has a double domination number.

Proof

Without loss of generality, let the underlying graph G=(V,E) of the signed graph Σ be connected. Then, the vertex set V itself is a double dominating set, for, as each vertex v dominates itself and G is connected without isolate vertices, there is a vertex u adjacent to v. Thus, both u and v dominate v. The remaining part with regard to the balance of Σ[V:V\V] is trivial. Thus, the existence of double dominating set for Σ is established. To prove the existence of a minimal double dominating set for Σ, we adopt the procedure that a vertex vV is removed from V by verifying the conditions that the remaining subset D=V\{v} is still a double dominating set for the underlying graph and Σ[D:V\D] is balanced. This removal procedure is continued till no more vertex may be moved to D satisfying the above criteria. This stage will give a minimal double dominating set. Among all the minimal double dominating sets, each of the smallest sets has cardinality γ×2(Σ).

Theorem 3.2

2γ×2(Σ)n for any signed graph Σ without isolated vertices and these bounds are sharp.

Proof

In order to find the lower bound, it is noted that for a vertex to be a member of any double dominating set, it must be adjacent to a vertex in that set. For the upper bound, we remarked that V itself is a double dominating set for a signed graph without isolated vertices. For the lower bound see Figure and for the upper bound see the signed star K1,n(r) .

Figure 9. γ×2(K4(4))=2.

Figure 9. γ×2(K4(4))=2.

Now we provide a bound for the double domination number in the case of signed graphs built on complete bipartite graphs Km,n which we denote by Km,n(r).

Theorem 3.3

4γ×2(Km,n(r))m+n-2 if m,n3.

Proof

For the lower bound, we use the inequality (Equation 5) and a result from Harary and Haynes (Citation2000) that γ×2(Km,n)=4 if m,n3. To obtain the upper bound, select one vertex one partite and keep it in the set D and other vertex from the next partite and keep in V\D in such a way that |D|=m+n-2 and |V\D|=2. This will make Σ[D:V\D] balanced and D becomes a double dominating set. Therefore, γ×2(Km,n(r))m+n-2

The sharpness of the upper bound is still open to explore. The lower bound is attained by the all-positive signed graph Km,n found in Harary and Haynes (Citation2000).

Figure 10. deg(u)=deg(v)=4.

Figure 10. deg(u)=deg(v)=4.

In addition to the distinctions between the double domination in unsigned graphs and that of signed graphs listed initially one more, regarding the lower bound in Theorem 3.2, it is given in Harary and Haynes (Citation2000 ) that in the case of unsigned graphs G, γ×2(G)=2 if and only if G has vertices u and v such that deg(u)=deg(v)=n-1. But this result fails generally in the case of a signed graph as illustrated in Figure .

Theorem 3.4

A signed graph Σ has V as its unique double dominating set if and only if for each vV there is a vertex with degree 1 in N[v].

Proof

If there is a vertex of degree 1 in N[v] for every vV, then as any double dominating set for a signed graph should include all its end vertices and their neigbhours, V is the unique double dominating set. Conversely, suppose Σ has V as its unique double dominating set. If there exists a vertex vV such that deg(v)2 and for all xN[v], deg(x)2, then V\{v} becomes a double dominating set since Σ[V\{v}:{v}] is balanced. This leads to a contradiction and the proof is complete.

Corollary 3.5

If there exists vV such that deg(x)2 for all xN[v], then γ×2(Σ)n-1.

Proof

Proof follows from Theorem 3.4.

4. Multiple domination

Generalizing the double domination, we now define k-tuple domination in signed graphs as follows.

Definition 4.1

Let Σ=(G,σ) be a signed graph where G=(V,E). A subset DV of vertices of Σ is a k-tuple dominating set of Σ, if it satisfies the following conditions: (i) every vertex u of Σ is either in D and u has at least k-1 neighbours in D or whenever uV\D, |N(u)D|k (ii)Σ[D:V\D] is balanced.

Also, the k-tuple dominating number of a signed graph Σ, denoted by γ×k(Σ), is the smallest number of vertices in a k-tuple dominating set. In particular, we have γ×1(Σ)=γ(Σ).

Many of the results valid for double domination in signed graphs hold good in the case of multiple domination also. The proofs of these results are nothing but simple generalizations of those in the case of double domination which are discussed in this paper. For completeness, we list these results without proof.

Theorem 4.2

k-tuple domination is invariant under switching.

Corollary 4.3

γ×k(Σ)=γ×k(Σζ)

In general,(7) γ×k(G)γ×k(Σ).(7)

Theorem 4.4

Every signed graph Σ=(G,σ) with δ(G)k-1 has a k-tuple dominating set and hence has a k-tuple domination number.

Regarding the bound, we have

Theorem 4.5

kγ×2(Σ)n for any signed graph Σδ(G)k-1 and these bounds are sharp.

Indeed, the upper bound and the lower bound are attained for the signed graph built on the complete graph Kk.

Theorem 4.6

If a vertex v has degree k-1, then N[v] must be a subset of every k-tuple dominating set.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

P.K. Ashraf

P.K. Ashraf is presently working as an assistant professor in the Department of Mathematics, Government Arts and Science College, Kondotty, Kerala, India. He has more than 4 years of research experience and 10 years of teaching experience. He has published his research findings in many recognized international journals.

K.A. Germina

K.A. Germina is currently a professor in Mathematics in University Botswana, Gaborone, Botswana. She has more than two decades of teaching experience and 15 years of research experience. She has more than a hundred research publications and she is the reviewer and editor for many journals and premiere reviewing services.

References

  • Acharya, B. D. (2013). Domination and absorbance in signed graphs and digraphs, I: Foundations. Journal of Combinatorial Mathematics and Combinatorial Computing, 84, 5–20.
  • Ashraf, P. K., & Germina, K. A. (2014). Neighbourhood balanced domination in signed graphs. International Journal of Mathematical Sciences and Engineering Applications, 8, 193–203.
  • Ashraf, P. K., & Germina, K. A. (2015). On minimal dominating sets for signed graphs. Advances and Applications in Discrete Mathematics, 15, 101–112.
  • Blidia, M., Chellali, M., Haynes, T. W., & Henning, M. (2006). Independent and double domination in trees. Utilitas Mathematica, 70, 159–173.
  • Chartrand, G., & Zang, P. (2009). Introduction to graph theory. New Delhi: Tata McGraw-Hill.
  • Germina, K. A., & Ashraf, P. K. (2013). On open domination and domination in signed graphs. International Mathematical Forum, 8, 1863–1872.
  • Germina, K. A., & Shahul Hameed, K. (2010). On signed paths, signed cycles and their energies. Applied Mathematical Science, 4, 3455–3466.
  • Germina, K. A., Shahul Hameed, K., & Zaslavsky, T. (2011). On product and line graphs of signed graphs, their eigenvalues and energy. Linear Algebra and its Applications, 435, 2432–2450.
  • Harary, F. (1972). Graph theory. Reading, MA: Addison Wesley.
  • Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2, 143–146.
  • Harary, F., & Haynes, T. (2000). Double domination in graphs. Ars Combinatoria, 55, 201–213.
  • Haynes, T., Hedetneimi, S. T., & Slater, P. J. (1998a). Fundamentals of domination in graphs. New York, NY: Marcel Dekker.
  • Haynes, T., Hedetniemi, S. T., & Slater, P. J. (1998b). Domination in graphs: Advanced topics. New York, NY: Marcel Dekker.
  • Zaslavsky, T. (1982). Signed graphs. Discrete Applied Mathematics, 4, 47–74 ( 1983, Erratum, Discrete Applied Mathematics, 5, 248).
  • Zaslavsky, T. (1998). A mathematical bibliography of signed and gain graphs and allied areas. Electronic Journal of Combinatorics, 8, DS8.