betaFeedback

WorksMathematics

Minimal super dominating sets of maximum cardinality

Abstract

Let G=(V,E)G = (V,E) be a graph. A subset S⊆VS \subseteq V of vertices is a super dominating set if every vertex v∈V−Sv \in V - S has a neighbour u∈Su \in S, whose only neighbour in V−SV - S is vv. A set S⊆VS \subseteq V is called open irredundant if every vertex u∈Su \in S has at least one neighbour v∈V−Sv \in V - S whose only neighbour in SS is uu. In this paper we establish connections between super dominating sets and open irredundant sets, similar to the connections that exist between dominating sets and irredundant sets. In particular, we define the new parameter Γsp(G)Γ_{sp}(G) as the maximum cardinality of a minimal super dominating set of GG and calculate Γsp(G)Γ_{sp}(G) for some families of graphs GG. Finally we present some properties of open irredundant sets and we will develop Gallai theorems involving domination, super domination and open irredundance parameters of graphs.

Introduction

Let G=(V,E)G = (V, E) a simple graph. A set vertex set S⊆VS \subseteq V is called independent if no two vertices in SS are adjacent. The vertex independence number α(G)\alpha(G) equals the maximum cardinality of an independent set of GG. A set S⊆VS \subseteq V is called a vertex cover if for every edge uv∈Euv \in E, either uu, or vv, or both uu and vv, are in SS. The vertex covering number β(G)\beta(G) equals the minimum cardinality of a vertex cover of GG. In 1959 Gallai [12] observed that a set S⊂VS \subset V is a maximal independent set if and only if the complement V−SV-S is a minimal vertex cover. From this it is straightforward to prove the following theorem.

Theorem 1.1. (Gallai [12]) For any graph GG of order n=∣V∣n = |V|, α(G)+β(G)=n\alpha(G) + \beta(G) = n.

Since 1959 many theorems of the form A(G)+B(G)=nA(G) + B(G) = n have been proven, where A(G)A(G) and B(G)B(G) are two maximum and minimum types of parameters of graphs. Results of this form are now called Gallai theorems. In 1988 Cockayne et al. [8] surveyed many Gallai theorems. Even more Gallai theorems are found in a 2002 paper by Balasubramanian et al. [1].

The open neighbourhood N(u)N(u) of a vertex uu in a graph GG is the set of vertices N(u)={v:uv∈E}N(u) = \{v : uv \in E\} which are adjacent to uu. The closed neighbourhood N[u]N[u] is the set N[u]=N(u)∪{u}N[u] = N(u) \cup\{u\}. The open (closed) neighbourhood N(S)N(S) (N[S]N[S]) of a set SS of vertices is the union of the open (closed) neighbourhoods N(u)N(u) (N[u]N[u]) of vertices u∈Su \in S. For a set SS of vertices, we say that a vertex u∈Su \in S has an external private neighbour with respect to SS if N(u)−N[S−{u}]≠∅N(u) - N[S - \{u\}] \ne\emptyset.

In this paper we are interested in the following three types of set of vertices in a graph.

A set SS of vertices is a dominating set if N[S]=VN[S] = V, or equivalently, if every vertex v∈V−Sv \in V-S has at least one neighbour in SS. The domination number γ(G)\gamma(G) of a graph GG equals the minimum cardinality of a dominating set of GG. A dominating set of GG with minimum cardinality is called a γ\gamma-set of GG.

A set S⊆VS \subseteq V is called a super dominating set of GG if every vertex v∈V−Sv \in V-S has an external private neighbour u∈Su \in S, with respect to V−SV-S. The super domination number γsp(G)\gamma_{sp}(G) equals the minimum cardinality of a super dominating set in a graph GG. A super dominating set of GG with minimum cardinality is called a γsp\gamma_{sp}-set of GG.

A set S⊆VS \subseteq V is called a open irredundant set of GG if every vertex u∈Su \in S has an external private neighbour with respect to SS. The open irredundance number oir⁡(G)\operatorname{oir}(G) equals the minimum cardinality of a maximal open irredundant set of GG. An open irredundant set of GG with minimum cardinality is called an oir⁡\operatorname{oir}-set of GG. Open irredundance was considered in [5, 6, 7, 10, 11].

The paper is organized in the following way: in the second section we recall the basic properties of a super domination in GG and we define the new parameter Γsp(G)\Gamma_{sp}(G) as the maximum cardinality of a minimal super dominating set of GG. We calculate Γsp(G)\Gamma_{sp}(G) for some families of graphs GG. In section three we present some properties of open irredundant set and we will develop Gallai theorems involving domination, super domination and open irredundance parameters of graphs.

Minimal super dominating sets of maximum cardinality

A set S⊆VS \subseteq V is a super dominating set of GG if for every vertex v∈V−Sv \in V-S, there exists a vertex u∈Su \in S such that N(u)∩(V−S)={v}N(u) \cap(V-S) = \{v\}. In the other words, SS is a super dominating set if every vertex v∈V−Sv \in V-S has an external private neighbour u∈Su \in S, with respect to V−SV-S. The super domination number γsp(G)\gamma_{sp}(G) equals the minimum cardinality of a super dominating set in a graph GG. Super dominating sets were defined in 2015 by Lemańska, Swaminathan, Venkatakrishnan and Zuazua [17]. In the paper the authors calculate the super dominating number for cycles and paths and observe that for any graph GG with order nn, γsp(G)≥n2\gamma_{sp}(G) \ge\frac{n}{2}. In Theorem 2.1, they give a characterization for connected graph GG with γsp(G)=n2\gamma_{sp}(G) = \frac{n}{2}. Moreover, in section 3, they show a characterization of trees which attain the lower and the upper bounds in terms of nn.

More properties of super dominating sets are studied in [9] and [15]. Recent papers on super domination include those by Krishnamurti and Venkatakrishnan [16] in 2016, Rodríguez-Velázquez, Klein, and Yi [19] in 2020, Senthilkumar, Venkatakrishnan and Naresh Kumar [20] and Zhuang [22] in 2022, Bujtás, Ghanbari and Klavžar [3] and Cabrera-Martínez and Conchalo Peiró [4] in 2023, and Ghanbari [13] and Ghanbari, Jäger and Lehtilä [14] in 2024.

We define the new parameter upper super domination number Γsp(G)\Gamma_{sp}(G) as the maximum cardinality of a minimal super dominating set of GG and a minimal superdominating set of GG with maximum cardinality we call a Γsp\Gamma_{sp}-set of GG. By definition, for any graph GG, γsp(G)≤Γsp(G)\gamma_{sp}(G) \le\Gamma_{sp}(G).

In the next proposition we show that the difference between Γsp(G)\Gamma_{sp}(G) and γsp(G)\gamma_{sp}(G) can be arbitrarily large.

Proposition 2.1. For any k∈N+k \in\mathbb{N}^{+} there exists a graph GG such that Γsp(G)−γsp(G)=k\Gamma_{sp}(G)-\gamma_{sp}(G)=k.

Proof. Consider a graph GG from Figure 1. On the left side there is GG with depicted in black vertices belonging to a γsp(G)\gamma_{sp}(G)-set and in the left side GG with depicted in black vertices belonging to a Γsp(G)\Gamma_{sp}(G)-set. ▪

Graph $G$ for which $\Gamma_{sp}(G)-\gamma_{sp}(G)=k$

Figure 1. Graph GG for which Γsp(G)−γsp(G)=k\Gamma_{sp}(G)-\gamma_{sp}(G)=k.

We now determine the upper super domination number of the path on nn vertices. We begin with determining this parameter for the first 21 paths. The following table show the exact value of Γsp(Pn)\Gamma_{sp}(P_n) for 2≤n≤212 \le n \le21.

nn234567891011
Γsp(Pn)\Gamma_{sp}(P_n)1223455677
nn12131415161718192021
Γsp(Pn)\Gamma_{sp}(P_n)891010111212131415

Table 1. Exact values of Γsp(Pn)\Gamma_{sp}(P_n) for 2≤n≤212 \le n \le21.

The vertices on the picture below on the left side of the paths form a minimal super dominating sets of maximum cardinality.

Paths $P_2$ through $P_{21}$ with minimal super dominating sets of maximum cardinality

Figure 3.

For n∈N+n \in\mathbb{N}^{+}, let PnP_n be a path with set of vertices {v1,…,vn}\{v_1,\ldots,v_n\} and set of edges {{vi,vi+1}∣i=1,…,n−1}\{\{v_i,v_{i+1}\}\mid i=1,\ldots,n-1\}. For i,j∈{1,…,n−1}i,j \in\{1,\ldots,n-1\} with i<ji<j, we will denote the subset {vi,vi+1,…,vj}\{v_i,v_{i+1},\ldots,v_j\} by [vi,vj][v_i,v_j].

Observation 2.2. Let n∈N+n \in\mathbb{N}^{+}, n>2n > 2. For every minimal super dominating set SS of PnP_n, ∣S∩[vn−2,vn]∣≤2|S \cap[v_{n-2},v_n]| \leq2.

Proof. If ∣S∩[vn−2,vn]∣=3|S\cap[v_{n-2},v_n]|=3, then S∖{vn}S\setminus\{v_n\} would be a super dominating set of PnP_n contradicting that SS is minimal.

Observation 2.3. Let n∈N+n \in\mathbb{N}^{+}, n>4n > 4. For every minimal superdominating set SS of PnP_n and every i∈{1,…,n−4}i \in\{1,\ldots,n-4\}, ∣S∩[vi,vi+4]∣≤4|S \cap[v_i,v_{i+4}]| \leq4.

Proof. If ∣S∩[vi,vi+4]∣=5|S\cap[v_i,v_{i+4}]|=5, then S∖{vi+2}S\setminus\{v_{i+2}\} would be a super dominating set of PnP_n contradicting that SS is minimal.

Observation 2.4. Let n∈N+n \in\mathbb{N}^{+}, n>5n > 5. For every minimal superdominating set SS of PnP_n, ∣S∩[vn−5,vn]∣≤4|S \cap[v_{n-5},v_n]| \leq4.

Proof. By Observation 2.3, ∣S∩[vn−5,vn]∣<6|S\cap[v_{n-5},v_n]|<6. Suppose ∣S∩[vn−5,vn]∣=5|S\cap[v_{n-5},v_n]|=5, by Observation 2.2, vn−5,vn−4,vn−3∈Sv_{n-5},v_{n-4},v_{n-3}\in S, and by Observation 2.3, vn∈Sv_n\in S. If vn−2∉Sv_{n-2}\notin S, then S∖{vn−3}S\setminus\{v_{n-3}\} would be a superdominating set of PnP_n contradicting that SS is minimal, and if vn−1∉Sv_{n-1}\notin S, then S∖{vn−2}S\setminus\{v_{n-2}\} would be a super dominating set of PnP_n contradicting that SS is minimal.

Lemma 2.5. Let n∈N+n \in\mathbb{N}^{+}, n>6n > 6. For every minimal superdominating set SS of PnP_n and every i∈{1,…,m−6}i\in\{1,\ldots,m-6\}, ∣S∩[vi,vi+6]∣≤5|S\cap[v_i,v_{i+6}]|\leq5.

Proof. Suppose ∣S∩[vi,vi+6]∣=7|S\cap[v_i,v_{i+6}]|=7, then S∖{vi+3}S\setminus\{v_{i+3}\} would be a super dominating set of PnP_n contradicting that SS is minimal.

Now, suppose ∣S∩[vi,vi+6]∣=6|S\cap[v_i,v_{i+6}]|=6, by Lemma 2.3, none five consecutive vertices belong to SS, so vi,vi+1,vi+2,vi+5,vi+6∈Sv_i,v_{i+1},v_{i+2},v_{i+5},v_{i+6}\in S, if vi+2∉Sv_{i+2}\notin S or vi+4∉Sv_{i+4}\notin S, then S∖{vi+3}S\setminus\{v_{i+3}\} would be a super dominating set of PnP_n, and if vi+3∉Sv_{i+3}\notin S, then S∖{vi+4}S\setminus\{v_{i+4}\} would be a super dominating set of PnP_n, contradicting in both cases that SS is minimal.

Proposition 2.6. Let n∈N+n\in\mathbb{N}^{+}. Let q,r∈Nq,r\in\mathbb{N} such that n=7q+rn=7q+r, with 0≤r<70\leq r<7. Then Γsp(Pn)≤5q+⌈2r3⌉\Gamma_{\mathrm{sp}}(P_n)\leq5q+\left\lceil\frac{2r}{3}\right\rceil.

Proof. Let SS be a minimal super dominating set of PnP_n. We consider some cases, depending from the value of rr.

Case 1: r=0r=0. By Lemma 2.5, every i∈{1,8,…,7(q−1)+1}i\in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S\cap[v_i,v_{i+6}]|\leq5, then

∣S∣=∑i=17(q−1)+1∣S∩[vi,vi+6]∣≤5q=5q+⌈2(0)3⌉.|S|=\sum_{i=1}^{7(q-1)+1}|S\cap[v_i,v_{i+6}]|\leq5q=5q+\left\lceil\frac{2(0)}{3}\right\rceil.

For the remaining cases, we see that if q=0q=0 the result is clear, because Γsp(P1)=Γsp(P2)=1\Gamma_{\mathrm{sp}}(P_1)=\Gamma_{\mathrm{sp}}(P_2)=1, Γsp(P3)=Γsp(P4)=2\Gamma_{\mathrm{sp}}(P_3)=\Gamma_{\mathrm{sp}}(P_4)=2, Γsp(P5)=3\Gamma_{\mathrm{sp}}(P_5)=3, Γsp(P6)=4\Gamma_{\mathrm{sp}}(P_6)=4 and all those values are less or equal to ⌈2r3⌉\left\lceil\frac{2r}{3}\right\rceil. Suppose now q>0q>0.

Case 2: r=1r=1. By Lemma 2.5, for every i∈{1,8,…,7(q−1)+1}i\in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S\cap[v_i,v_{i+6}]|\leq5, then

∣S∣=(∑i=17(q−1)+1∣S∩[vi,vi+6]∣)+∣S∩{vn}∣≤5q+1=5q+⌈2(1)3⌉.|S|=\left(\sum_{i=1}^{7(q-1)+1}|S\cap[v_i,v_{i+6}]|\right)+|S\cap\{v_n\}|\leq5q+1=5q+\left\lceil\frac{2(1)}{3}\right\rceil.

Case 3: r=2r = 2. By Lemma 2.5, for every i∈{1,8,…,7(q−1)+1}i \in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S \cap[v_i,v_{i+6}]| \le5, then

∣S∣=(∑i=17(q−1)+1∣S∩[vi,vi+6]∣)+∣S∩{vn−1,vn}∣≤5q+2=5q+⌈2(2)3⌉.|S| = \left(\sum_{i=1}^{7(q-1)+1}|S \cap[v_i,v_{i+6}]|\right) + |S \cap\{v_{n-1},v_n\}| \le5q+2 = 5q + \left\lceil\frac{2(2)}{3}\right\rceil.

Case 4: r=3r = 3. By Lemma 2.5, for every i∈{1,8,…,7(q−1)+1}i \in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S \cap[v_i,v_{i+6}]| \le5, and by Observation 2.2, ∣S∩[vn−2,vn]∣≤2|S \cap[v_{n-2},v_n]| \le2, then

∣S∣=(∑i=17(q−1)+1∣S∩[vi,vi+6]∣)+∣S∩[vn−2,vn]∣≤5q+2=5q+⌈2(3)3⌉.|S| = \left(\sum_{i=1}^{7(q-1)+1}|S \cap[v_i,v_{i+6}]|\right) + |S \cap[v_{n-2},v_n]| \le5q+2 = 5q + \left\lceil\frac{2(3)}{3}\right\rceil.

Case 5: r=4r = 4. By Lemma 2.5, for every i∈{1,8,…,7(q−1)+1}i \in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S \cap[v_i,v_{i+6}]| \le5, and by Observation 2.2, ∣S∩[vn−2,vn]∣≤2|S \cap[v_{n-2},v_n]| \le2, then

∣S∣=(∑i=17(q−1)+1∣S∩[vi,vi+6]∣)+∣S∩{vn−3}∣+∣S∩[vn−2,vn]∣|S| = \left(\sum_{i=1}^{7(q-1)+1}|S \cap[v_i,v_{i+6}]|\right) + |S \cap\{v_{n-3}\}| + |S \cap[v_{n-2},v_n]|
≤5q+1+2=5q+3=5q+⌈2(4)3⌉.\le5q+1+2 = 5q+3 = 5q + \left\lceil\frac{2(4)}{3}\right\rceil.

Case 6: r=5r = 5. By Lemma 2.5, for every i∈{1,8,…,7(q−1)+1}i \in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S \cap[v_i,v_{i+6}]| \le5, and by Observation 2.3, ∣S∩[vn−4,vn]∣≤4|S \cap[v_{n-4},v_n]| \le4, then

∣S∣=(∑i=17(q−1)+1∣S∩[vi,vi+6]∣)+∣S∩[vn−4,vn]∣≤5q+4=5q+⌈2(5)3⌉.|S| = \left(\sum_{i=1}^{7(q-1)+1}|S \cap[v_i,v_{i+6}]|\right) + |S \cap[v_{n-4},v_n]| \le5q+4 = 5q + \left\lceil\frac{2(5)}{3}\right\rceil.

Case 7: r=6r = 6. By Lemma 2.5, for every i∈{1,8,…,7(q−1)+1}i \in\{1,8,\ldots,7(q-1)+1\}, ∣S∩[vi,vi+6]∣≤5|S \cap[v_i,v_{i+6}]| \le5, and by Observation 2.4, ∣S∩[vn−5,vn]∣≤4|S \cap[v_{n-5},v_n]| \le4, then

∣S∣=(∑i=17(q−1)+1∣S∩[vi,vi+6]∣)+∣S∩[vn−5,vn]∣≤5q+4=5q+⌈2(6)3⌉.|S| = \left(\sum_{i=1}^{7(q-1)+1}|S \cap[v_i,v_{i+6}]|\right) + |S \cap[v_{n-5},v_n]| \le5q+4 = 5q + \left\lceil\frac{2(6)}{3}\right\rceil.

In all cases Γsp(Pn)≤∣S∣≤5q+⌈2r3⌉\Gamma_{\mathrm{sp}}(P_n) \le|S| \le5q + \left\lceil\frac{2r}{3}\right\rceil.

Proposition 2.7. Let n∈N+n \in\mathbb{N}^{+}, n≥5n \ge5. Let q,r∈Nq,r \in\mathbb{N} such that n=21q+rn = 21q+r, with 0≤r<210 \le r < 21. Then Γsp(Pn)≥15q\Gamma_{\mathrm{sp}}(P_n) \ge15q if r=0,1r = 0,1, and Γsp(Pn)≥15q+⌈2r−13⌉\Gamma_{\mathrm{sp}}(P_n) \ge15q + \left\lceil\frac{2r-1}{3}\right\rceil if 2≤r<212 \le r < 21.

Proof. For each j∈{0,1,…,q}j \in\{0,1,\ldots,q\} let B0=∅B_0 = \varnothing and Bj={v21(j−1)+k∣k∈{1,2,4,6,7,8,9,11,13,14,15,16,18,20,21}}B_j = \{v_{21(j-1)+k} \mid k \in\{1,2,4,6,7,8,9,11,13,14,15,16,18,20,21\}\} if j>0j > 0.

If r=0r = 0 or r=1r = 1, then the set S=⋃j=0qBjS = \bigcup_{j=0}^{q}B_j is a minimal super dominating set of PnP_n with ∣S∣=15q|S| = 15q. Then, Γsp(Pn)≥∣S∣=15q\Gamma_{\mathrm{sp}}(P_n) \ge|S| = 15q.

For r≥2r \ge2 define:

  • if r=16r = 16, Tn={v21q+k∣k∈{1,…,r−1},k≢3(mod7),k≢5(mod7)}T_n = \{v_{21q+k} \mid k \in\{1,\ldots,r-1\}, k \not\equiv3 \pmod7, k \not\equiv5 \pmod7\},

  • if r≡1(mod3)r \equiv1 \pmod3 and r≠16r \ne16, Tn={v21q+k∣k∈{1,…,r},k≢3(mod7),k≢5(mod7)}T_n = \{v_{21q+k} \mid k \in\{1,\ldots,r\}, k \not\equiv3 \pmod7, k \not\equiv5 \pmod7\},

  • if r≡2(mod6)r \equiv2 \pmod6, Tn={v21q+k∣k∈{1,…,r−2},k≢3(mod6),k≢4(mod6)}∪{vn−1}T_n = \{v_{21q+k} \mid k \in\{1,\ldots,r-2\}, k \not\equiv3 \pmod6, k \not\equiv4 \pmod6\} \cup\{v_{n-1}\},

  • if r≢1(mod3)r \not\equiv1 \pmod3 and r≢2(mod6)r \not\equiv2 \pmod6, Tn={v21q+k∣k∈{1,…,r},k≢3(mod6),k≢4(mod6)}T_n = \{v_{21q+k} \mid k \in\{1,\ldots,r\}, k \not\equiv3 \pmod6, k \not\equiv4 \pmod6\}.

The set S=(⋃j=0qBj)∪TnS=\left(\bigcup_{j=0}^{q}B_j\right)\cup T_n is a minimal super dominating set of PnP_n with ∣S∣=15q+⌈2r−13⌉|S|=15q+\left\lceil\frac{2r-1}{3}\right\rceil. Then, Γsp(Pn)≥∣S∣=15q+⌈2r−13⌉\Gamma_{sp}(P_n)\ge|S|=15q+\left\lceil\frac{2r-1}{3}\right\rceil.

Theorem 2.8. Let n∈N+n\in\mathbb{N}^{+}. Let q,r∈Nq,r\in\mathbb{N} such that n=21q+rn=21q+r, with 0≤r<200\le r<20 and k,t∈Nk,t\in\mathbb{N} such that r=7k+tr=7k+t, with 0≤t<70\le t<7. Then Γsp(Pn)=15q+5k+⌈2t3⌉\Gamma_{sp}(P_n)=15q+5k+\left\lceil\frac{2t}{3}\right\rceil or Γsp(Pn)=15q+5k+⌈2t3⌉−1\Gamma_{sp}(P_n)=15q+5k+\left\lceil\frac{2t}{3}\right\rceil-1.

Proof. We consider some cases, depending on the values of rr. The cases n∈{2,3,4}n\in\{2,3,4\} are immediate, so we may assume that n≥5n\ge5.

Case 1: r=0r=0. In this case n=21q+rn=21q+r, with r=0r=0, and r=7k+tr=7k+t, with k=t=0k=t=0. As n=21q+r=7(3q)+rn=21q+r=7(3q)+r with r=0r=0, by Proposition 2.6, Γsp(Pn)≤5(3q)+⌈2r3⌉=15q\Gamma_{sp}(P_n)\le5(3q)+\left\lceil\frac{2r}{3}\right\rceil=15q, and by Proposition 2.7, Γsp(Pn)≥15q\Gamma_{sp}(P_n)\ge15q. Then, Γsp(Pn)=15q=15q+5k+⌈2t3⌉\Gamma_{sp}(P_n)=15q=15q+5k+\left\lceil\frac{2t}{3}\right\rceil.

Case 2: r=1r=1. In this case n=21q+rn=21q+r, with r=1r=1, and r=7k+tr=7k+t, with k=0k=0 and t=1t=1. As n=21q+r=7(3q)+rn=21q+r=7(3q)+r with r=1r=1, by Proposition 2.6, Γsp(Pn)≤5(3q)+⌈2r3⌉=15q+⌈23⌉\Gamma_{sp}(P_n)\le5(3q)+\left\lceil\frac{2r}{3}\right\rceil=15q+\left\lceil\frac{2}{3}\right\rceil, and by Proposition 2.7, Γsp(Pn)≥15q\Gamma_{sp}(P_n)\ge15q, and 15q=15q+⌈23⌉−115q=15q+\left\lceil\frac{2}{3}\right\rceil-1. Then, Γsp(Pn)=15q+⌈23⌉=15q+⌈2t3⌉\Gamma_{sp}(P_n)=15q+\left\lceil\frac{2}{3}\right\rceil=15q+\left\lceil\frac{2t}{3}\right\rceil or Γsp(Pn)=15q+⌈23⌉−1=15q+⌈2t3⌉−1\Gamma_{sp}(P_n)=15q+\left\lceil\frac{2}{3}\right\rceil-1=15q+\left\lceil\frac{2t}{3}\right\rceil-1.

Case 3: 2≤r2\le r. As n=21q+rn=21q+r, with 2≤r<202\le r<20 and k,t∈Nk,t\in\mathbb{N} such that r=7k+tr=7k+t, with 0≤t<70\le t<7, then n=7(3q)+7k+t=7(3q+k)+tn=7(3q)+7k+t=7(3q+k)+t, so by Proposition 2.6,

Γsp(Pn)≤5(3q+k)+⌈2t3⌉=15q+5k+⌈2t3⌉.\Gamma_{sp}(P_n)\le5(3q+k)+\left\lceil\frac{2t}{3}\right\rceil=15q+5k+\left\lceil\frac{2t}{3}\right\rceil.

Now, by Proposition 2.7,

Γsp(Pn)≥15q+⌈2r−13⌉=15q+⌈2(7k+t)−13⌉=15q+⌈15k+2t−k−13⌉=15q+5k+⌈2t−k−13⌉,\begin{aligned} \Gamma_{sp}(P_n)\ge15q+\left\lceil\frac{2r-1}{3}\right\rceil=15q+\left\lceil\frac{2(7k+t)-1}{3}\right\rceil=15q+\left\lceil\frac{15k+2t-k-1}{3}\right\rceil\\ &=15q+5k+\left\lceil\frac{2t-k-1}{3}\right\rceil, \end{aligned}

but, r=7k+tr=7k+t and 2≤r<202\le r<20, so k∈{0,1,2}k\in\{0,1,2\}. Then, ⌈2t−k−13⌉=⌈2t3⌉\left\lceil\frac{2t-k-1}{3}\right\rceil=\left\lceil\frac{2t}{3}\right\rceil (when k=0k=0 and t≢2(mod⁡3)t\not\equiv2(\operatorname{mod}3), or when k=1k=1 and t≡0(mod⁡3)t\equiv0(\operatorname{mod}3)), or ⌈2t−k−13⌉=⌈2t3⌉−1\left\lceil\frac{2t-k-1}{3}\right\rceil=\left\lceil\frac{2t}{3}\right\rceil-1 in the remaining cases, so

Γsp(Pn)≥15q+5k+⌈2t3⌉\Gamma_{sp}(P_n)\ge15q+5k+\left\lceil\frac{2t}{3}\right\rceil

or

Γsp(Pn)≥15q+5k+⌈2t3⌉−1.\Gamma_{sp}(P_n)\ge15q+5k+\left\lceil\frac{2t}{3}\right\rceil-1.

We conclude that Γsp(Pn)=15q+5k+⌈2t3⌉\Gamma_{sp}(P_n)=15q+5k+\left\lceil\frac{2t}{3}\right\rceil or Γsp(Pn)=15q+5k+⌈2t3⌉−1\Gamma_{sp}(P_n)=15q+5k+\left\lceil\frac{2t}{3}\right\rceil-1.

By the analysis made in the proof of Theorem 2.8, we have the following

Corollary 2.9. Let n∈N+n\in\mathbb{N}^{+}. Let q,r∈Nq,r\in\mathbb{N} such that n=21q+rn=21q+r, with 0≤r<200\le r<20 and k,t∈Nk,t\in\mathbb{N} such that r=7k+tr=7k+t, with 0≤t<70\le t<7. In the following cases:

(a) r=0r=0, or

(b) 2≤r2\le r, k=0k=0 and t≢2(mod⁡3)t\not\equiv2(\operatorname{mod}3), or

(c) 2≤r2\le r, k=1k=1 and t≡0(mod⁡3)t\equiv0(\operatorname{mod}3),

we have that Γsp(Pn)=15q+5k+⌈2t3⌉\Gamma_{sp}(P_n)=15q+5k+\left\lceil\frac{2t}{3}\right\rceil.

Now we consider the case of cycles. For n∈N+n \in\mathbb{N}^{+}, let CnC_n be the cycle with set of vertices {v1,…,vn}\{v_1,\ldots,v_n\} and set of edges {{vi,vi+1}∣i=1,…,n−1}∪{vn,v1}\{\{v_i,v_{i+1}\}\mid i=1,\ldots,n-1\}\cup\{v_n,v_1\}.

Lemma 2.10. Let n∈N+n \in\mathbb{N}^{+}, n>2n>2. For every minimal super dominating set SS of CnC_n, there exist two adjacent vertices u,v∈V(G)u,v \in V(G) of CnC_n such that u,v∈Su,v \in S.

Proof. Let SS be a minimal super dominating set of CnC_n. Consider w∈V−Sw \in V-S; as SS is a super dominating set, ww has an external private neighbour u∈Su \in S with respect to V−SV-S. Then, as uu is an external private neighbour with respect to V−SV-S, v∈N(u)−{w}v \in N(u)-\{w\} is in SS. ■

Lemma 2.11. Let SS be a Γsp(Cn)\Gamma_{sp}(C_n)-set and let u,vu,v be adjacent vertices in SS. Then any longest path PP in CnC_n with V(P)⊆SV(P)\subseteq S and u,v∈V(P)u,v \in V(P) has a length ll satisfying 1≤l≤31\leq l\leq3.

Proof. Suppose by contradiction that PP has length more than three; then there exists a path P5=x1x2x3x4x5P_5=x_1x_2x_3x_4x_5 contained in PP. But in that case S−{x3}S-\{x_3\} is a super dominating set of CnC_n with cardinality ∣S∣−1|S|-1, a contradiction with minimality of SS. Thus P=PmP=P_m with m∈{2,3,4}m\in\{2,3,4\}. ■

Proposition 2.12. For every integer n≥3n\geq3, we have Γsp(Cn)≤Γsp(Pn)\Gamma_{sp}(C_n)\leq\Gamma_{sp}(P_n).

Proof. Let SS be a Γsp(Cn)\Gamma_{sp}(C_n)-set and consider two vertices u,vu,v adjacent in SS. Let PmP_m be a longest path with V(Pm)⊆SV(P_m)\subseteq S and u,v∈V(Pm)u,v\in V(P_m); from Lemma 2.11 m∈{2,3,4}m\in\{2,3,4\}.

  • If m=2m=2, then SS is a minimal super dominating set of PnP_n, where Pn=Cn−{uv}P_n=C_n-\{uv\};

  • If m=3m=3 and P3=x1x2x3P_3=x_1x_2x_3, then SS is a minimal super dominating set of PnP_n, where Pn=Cn−{x1x2}P_n=C_n-\{x_1x_2\};

  • If m=4m=4 and P4=x1x2x3x4P_4=x_1x_2x_3x_4, then SS is a minimal super dominating set of PnP_n, where Pn=Cn−{x2x3}P_n=C_n-\{x_2x_3\}.

Then, Γsp(Cn)=∣S∣≤Γsp(Pn)\Gamma_{sp}(C_n)=|S|\leq\Gamma_{sp}(P_n). ■

Finally, we consider minimal super dominating sets of maximum cardinality in caterpillars. For m∈N+m\in\mathbb{N}^{+} with m>2m>2, let OmO_m be a caterpillar graph with set of vertices {v1,…,vm}∪{w1,…,wm}\{v_1,\ldots,v_m\}\cup\{w_1,\ldots,w_m\} and set of edges {{vi,vi+1}∣i=1,…,m−1}∪{{vi,wi}∣i=1,…,m}\{\{v_i,v_{i+1}\}\mid i=1,\ldots,m-1\}\cup\{\{v_i,w_i\}\mid i=1,\ldots,m\}. Notice that ∣V(Om)∣=2m|V(O_m)|=2m.

Lemma 2.13. Let m∈N+m\in\mathbb{N}^{+} with m>2m>2. For every minimal super dominating set of OmO_m, ∣S∩{v1,w1}∣=∣S∩{vm,wm}∣=1|S\cap\{v_1,w_1\}|=|S\cap\{v_m,w_m\}|=1.

Proof. As w1w_1 must be dominated by SS, then S∩{v1,w1}≠∅S\cap\{v_1,w_1\}\neq\varnothing. Suppose by contradiction that S∩{v1,w1}={v1,w1}S\cap\{v_1,w_1\}=\{v_1,w_1\}, then, as S−{w1}S-\{w_1\} is not a super dominating set, b1b_1 would not have a private neighbour with respect to V−(S−{w1})V-(S-\{w_1\}), so v2∉Sv_2\notin S, but this implies, as w2w_2 must be dominated by SS, w2∈Sw_2\in S. Then S−{v1}S-\{v_1\} would be a super dominating set, which is a contradiction.

We conclude ∣S∩{v1,w1}∣=1|S\cap\{v_1,w_1\}|=1. Similarly, ∣S∩{vm,wm}∣=1|S\cap\{v_m,w_m\}|=1. ■

Lemma 2.14. Let m∈N+m\in\mathbb{N}^{+} with m>2m>2. For every minimal super dominating set of OmO_m and for every i∈{1,2,…,m−1}i\in\{1,2,\ldots,m-1\}, ∣S∩{vi,wi,vi+1,wi+1}∣≤3|S\cap\{v_i,w_i,v_{i+1},w_{i+1}\}|\leq3.

Proof. Suppose by contradiction that ∣S∩{vi,wi,vi+1,wi+1}∣=4|S \cap\{v_i,w_i,v_{i+1},w_{i+1}\}|=4. By Lemma 2.13, i≠1i \ne1 and i≠n−1i \ne n-1. As S−{wi}S-\{w_i\} is not a super dominating set, vi−1∉Sv_{i-1} \notin S. Also, as S−{wi+1}S-\{w_{i+1}\} is not a super dominating set, vi+1∉Sv_{i+1} \notin S. As consequence, wi−1,wi+1∈Sw_{i-1},w_{i+1} \in S, otherwise they would not have a private neighbour with respect to V−SV-S. Then, S−{wi,wi+1}S-\{w_i,w_{i+1}\} would be a super dominating set, which is a contradiction.

We conclude ∣S∩{vi,wi,vi+1,wi+1}∣≤3|S \cap\{v_i,w_i,v_{i+1},w_{i+1}\}| \le3.

Theorem 2.15. Let m>2m>2. Then, Γsp(Om)={3q+1,if m=2q+1, q≥1,3q+2,if m=2q+2, q≥1.\Gamma_{sp}(O_m)=\begin{cases}3q+1, & \text{if }m=2q+1,\ q\ge1,\\3q+2, & \text{if }m=2q+2,\ q\ge1.\end{cases}

Proof. First we will prove that Γsp(Om)≥{3q+1,if m=2q+1, q≥1,3q+2,if m=2q+2, q≥1.\Gamma_{sp}(O_m)\ge\begin{cases}3q+1, & \text{if }m=2q+1,\ q\ge1,\\3q+2, & \text{if }m=2q+2,\ q\ge1.\end{cases}

We consider some cases, depending on the value of mm. Minimal super dominating sets of maximum cardinality of OmO_m are marked on Figure 2 (PDF p. 9).

Figure 2 (PDF p. 9). Minimal super dominating sets of maximum cardinality of OmO_m

Case 1: m=2q+1m=2q+1, with q≥1q\ge1.

  1. For m≡1(mod4)m\equiv1\pmod{4} the set

Sm={vj∣1≤j≤m, j≢3(mod4)}∪{wj∣1≤j<m, j≢1(mod4)}S_m=\{v_j\mid1\le j\le m,\ j\not\equiv3\pmod{4}\}\cup\{w_j\mid1\le j<m,\ j\not\equiv1\pmod{4}\}

is a minimal super dominating set of OmO_m, so Γsp(Om)≥∣Sm∣=6(m−14)+1=6(2q4)+1=3q+1\Gamma_{sp}(O_m)\ge|S_m|=6\left(\frac{m-1}{4}\right)+1=6\left(\frac{2q}{4}\right)+1=3q+1.

  1. For m≡3(mod4)m\equiv3\pmod{4}, the set

Sm={vj∣1≤j≤m, j≢3(mod4)}∪{wj∣1≤j≤m, j≢1(mod4)}S_m=\{v_j\mid1\le j\le m,\ j\not\equiv3\pmod{4}\}\cup\{w_j\mid1\le j\le m,\ j\not\equiv1\pmod{4}\}

is a minimal super dominating set of OmO_m, so Γsp(Om)≥∣Sm∣=6(m−34)+4=6(2q−24)+4=3(q−1)+4=3q+1\Gamma_{sp}(O_m)\ge|S_m|=6\left(\frac{m-3}{4}\right)+4=6\left(\frac{2q-2}{4}\right)+4=3(q-1)+4=3q+1.

Case 2: m=2q+2m=2q+2, with q≥1q\ge1.

(a) For m≡0(mod4)m\equiv0\pmod{4}, the set

Sm={vj∣1≤j≤m−4, j≢3(mod4)}∪{wj∣1≤j≤m−4, j≢1(mod4)}∪{vm−3,vm−2,wm−2,wm−1,wm}\begin{aligned} S_m={}&\{v_j\mid1\le j\le m-4,\ j\not\equiv3\pmod{4}\}\cup\{w_j\mid1\le j\le m-4,\ j\not\equiv1\pmod{4}\}\\ &\cup\{v_{m-3},v_{m-2},w_{m-2},w_{m-1},w_m\} \end{aligned}

is a minimal super dominating set of OmO_m, so Γsp(Om)≥∣Sm∣=6(m−44)+5=6(2q−24)+5=3(q−1)+5=3q+2\Gamma_{sp}(O_m)\ge|S_m|=6\left(\frac{m-4}{4}\right)+5=6\left(\frac{2q-2}{4}\right)+5=3(q-1)+5=3q+2.

(b) For m≡2(mod4)m\equiv2\pmod{4}, the set

Sm={vj∣1≤j≤m, j≢3(mod4)}∪{wj∣1≤j≤m−2, j≢1(mod4)}S_m=\{v_j\mid1\le j\le m,\ j\not\equiv3\pmod{4}\}\cup\{w_j\mid1\le j\le m-2,\ j\not\equiv1\pmod{4}\}

is a minimal super dominating set of OmO_m, so Γsp(Om)≥∣Sm∣=6(m−24)+2=6(2q4)+2=3q+2\Gamma_{sp}(O_m)\ge|S_m|=6\left(\frac{m-2}{4}\right)+2=6\left(\frac{2q}{4}\right)+2=3q+2.

Now, we will prove that Γsp(Om)≤{3q+1,if m=2q+1, q≥1,3q+2,if m=2q+2, q≥1.\Gamma_{sp}(O_m)\le\begin{cases}3q+1, & \text{if }m=2q+1,\ q\ge1,\\3q+2, & \text{if }m=2q+2,\ q\ge1.\end{cases}

Let SmS_m be a minimal super dominating set of OmO_m. Similarly like before, we consider some cases depending on the value of mm. Case 1: m=2q+1m=2q+1, with q≥1q\ge1. Using Lemma 2.13 and Lemma 2.14 we have that

∣Sm∣=∣Sm∩{v1,w1}∣+∑i=1q∣Sm∩{v2i,w2i,v2i+1,w2i+1}∣≤1+3q.|S_m|=|S_m\cap\{v_1,w_1\}|+\sum_{i=1}^{q}|S_m\cap\{v_{2i},w_{2i},v_{2i+1},w_{2i+1}\}|\le1+3q.

Case 2: m=2q+2m=2q+2, with q≥1q\ge1. Using Lemma 2.13 and Lemma 2.14 we have

∣Sm∣=∣Sm∩{v1,w1}∣+∣Sm∩{vm,wm}∣+∑i=1q∣Sm∩{v2i,w2i,v2i+1,w2i+1}∣|S_m|=|S_m\cap\{v_1,w_1\}|+|S_m\cap\{v_m,w_m\}|+\sum_{i=1}^{q}|S_m\cap\{v_{2i},w_{2i},v_{2i+1},w_{2i+1}\}|
≤1+1+3q=3q+2.\le1+1+3q=3q+2.

We conclude

Γsp(Om)={3q+1,if m=2q+1, q≥1,3q+2,if m=2q+2, q≥1.\Gamma_{sp}(O_m)= \begin{cases} 3q+1, & \text{if }m=2q+1,\ q\ge1,\\ 3q+2, & \text{if }m=2q+2,\ q\ge1. \end{cases}

Some Gallai-type theorems

In this section we present some Gallai-type theorems involving dominating, super dominating and open irredundant sets.

Relations between Γsp(G)\Gamma_{sp}(G) and γ(G)\gamma(G)

The calculations we showed in the previous section lead us to the following two propositions.

Proposition 3.1. Let n∈N+n \in\mathbb{N}^{+}. Then, γ(Pn)+Γsp(Pn)≥n\gamma(P_n) + \Gamma_{sp}(P_n) \ge n.

Proof. Let q,r∈Nq,r \in\mathbb{N} such that n=21q+rn=21q+r, with 0≤r<210 \le r < 21. For 2≤n≤42 \le n \le4, we have the equality γ(Pn)+Γsp(Pn)=n\gamma(P_n)+\Gamma_{sp}(P_n)=n. For n≥5n \ge5, we know that γ(Pn)=⌈n3⌉\gamma(P_n)=\left\lceil\frac{n}{3}\right\rceil and by Proposition 2.7 Γsp(Pn)≥15q+⌈2r−13⌉\Gamma_{sp}(P_n) \ge15q+\left\lceil\frac{2r-1}{3}\right\rceil so,

γ(Pn)+Γsp(Pn)≥⌈n3⌉+15q+⌈2r−13⌉=⌈21q+r3⌉+15q+⌈2r−13⌉=7q+⌈r3⌉+15q+⌈2r−13⌉=22q+⌈r3⌉+⌈2r−13⌉.\begin{aligned} \gamma(P_n)+\Gamma_{sp}(P_n) &\ge\left\lceil\frac{n}{3}\right\rceil+15q+\left\lceil\frac{2r-1}{3}\right\rceil=\left\lceil\frac{21q+r}{3}\right\rceil+15q+\left\lceil\frac{2r-1}{3}\right\rceil\\ &=7q+\left\lceil\frac{r}{3}\right\rceil+15q+\left\lceil\frac{2r-1}{3}\right\rceil=22q+\left\lceil\frac{r}{3}\right\rceil+\left\lceil\frac{2r-1}{3}\right\rceil. \end{aligned}

We consider some cases, depending on the value of rr.

Case 1: r=3ρr=3\rho, ρ∈N\rho\in\mathbb{N}.

γ(Pn)+Γsp(Pn)≥22q+⌈r3⌉+⌈2r−13⌉=22q+⌈3ρ3⌉+⌈2(3ρ)−13⌉=22q+ρ+2ρ=q+(21q+3ρ)=q+n≥n.\begin{aligned} \gamma(P_n)+\Gamma_{sp}(P_n)&\ge22q+\left\lceil\frac{r}{3}\right\rceil+\left\lceil\frac{2r-1}{3}\right\rceil=22q+\left\lceil\frac{3\rho}{3}\right\rceil+\left\lceil\frac{2(3\rho)-1}{3}\right\rceil\\ &=22q+\rho+2\rho=q+(21q+3\rho)=q+n\ge n. \end{aligned}

Case 2: r=3ρ+1r=3\rho+1, ρ∈N\rho\in\mathbb{N}.

γ(Pn)+Γsp(Pn)≥22q+⌈r3⌉+⌈2r−13⌉=22q+⌈3ρ+13⌉+⌈2(3ρ+1)−13⌉=22q+ρ+1+2ρ+1=q+(21q+3ρ+1)+1=q+n+1>n.\begin{aligned} \gamma(P_n)+\Gamma_{sp}(P_n)&\ge22q+\left\lceil\frac{r}{3}\right\rceil+\left\lceil\frac{2r-1}{3}\right\rceil=22q+\left\lceil\frac{3\rho+1}{3}\right\rceil+\left\lceil\frac{2(3\rho+1)-1}{3}\right\rceil\\ &=22q+\rho+1+2\rho+1=q+(21q+3\rho+1)+1=q+n+1>n. \end{aligned}

Case 3: r=3ρ+2r=3\rho+2, ρ∈N\rho\in\mathbb{N}.

γ(Pn)+Γsp(Pn)≥22q+⌈r3⌉+⌈2r−13⌉=22q+⌈3ρ+23⌉+⌈2(3ρ+2)−13⌉=22q+ρ+1+2ρ+1=q+(21q+3ρ+2)=q+n≥n.\begin{aligned} \gamma(P_n)+\Gamma_{sp}(P_n)&\ge22q+\left\lceil\frac{r}{3}\right\rceil+\left\lceil\frac{2r-1}{3}\right\rceil=22q+\left\lceil\frac{3\rho+2}{3}\right\rceil+\left\lceil\frac{2(3\rho+2)-1}{3}\right\rceil\\ &=22q+\rho+1+2\rho+1=q+(21q+3\rho+2)=q+n\ge n. \end{aligned}

We conclude that γ(Pn)+Γsp(Pn)≥n\gamma(P_n)+\Gamma_{sp}(P_n)\ge n.

Observation 3.2. Notice that there exist n∈N+n \in\mathbb{N}^{+} such that γ(Pn)+Γsp(Pn)>n\gamma(P_n)+\Gamma_{sp}(P_n)>n, for example n=21q+rn=21q+r, with q,r∈Nq,r \in\mathbb{N}, 0≤r<210\le r<21 and q>0q>0.

The following proposition shows the strict inequality fulfill for caterpillars:

Proposition 3.3. Let m∈N+m \in\mathbb{N}^{+} with m>2m>2. Then, γ(Om)+Γsp(Om)>2m\gamma(O_m)+\Gamma_{sp}(O_m)>2m.

Proof. Let m∈N+m \in\mathbb{N}^{+} with m>2m>2. Consider the following cases:

Case1: m=2q+1m=2q+1, with q≥1q\ge1. By Proposition 2.15, Γsp(Om)=3q+1\Gamma_{sp}(O_m)=3q+1. Also, Dm={vj∣j=1,…,m}D_m=\{v_j\mid j=1,\ldots,m\} is a dominating set of OmO_m of minimum cardinality, so γ(Om)=∣Dm∣=m\gamma(O_m)=|D_m|=m. Then,

γ(Om)+Γsp(Cm)=m+3q+1=2q+1+3q+1=6q+2>4q+2=2m.\gamma(O_m)+\Gamma_{sp}(C_m)=m+3q+1=2q+1+3q+1=6q+2>4q+2=2m.

Case 2: m=2q+2m=2q+2, with q≥1q\ge1. By Proposition 2.15, Γsp(Om)=3q+2\Gamma_{sp}(O_m)=3q+2. Also, Dm={vj∣j=1,…,m}D_m=\{v_j\mid j=1,\ldots,m\} is a dominating set of OmO_m of minimum cardinality, so γ(Om)=∣Dm∣=m\gamma(O_m)=|D_m|=m. Then,

γ(Om)+Γsp(Om)≥m+3q+2=2q+2+3q+2=6q+4>4q+4=2m.\gamma(O_m)+\Gamma_{sp}(O_m)\ge m+3q+2=2q+2+3q+2=6q+4>4q+4=2m.

In 1979 Bollobás and Cockayne [2] proved the following now well-known result.

Theorem 3.4. (Bollobás-Cockayne [2]) Every isolate-free graph GG contains an open irredundant γ\gamma-set, that is a minimum cardinality dominating set SS in which every vertex u∈Su \in S has at least one external private neighbour.

With this in mind we can prove the following result, which will be useful to establish a relation between the domination number γ(G)\gamma(G) and the upper super domination number Γsp(G)\Gamma_{sp}(G).

Lemma 3.5. If DD is a γ\gamma-set in a graph GG that is open irredundant, then V−DV-D is a minimal super dominating set of GG.

Proof. Let DD be a γ\gamma-set in a graph GG that is open irredundant. Thus, DD is a private dominating set and from Proposition 3.14, we have that V−DV-D is a super dominating set. Assume that V−DV-D is not a minimal super dominating set; thus there exists a vertex x∈V−Dx \in V-D such that (V−D)−{x}(V-D)-\{x\} is a super dominating set. Hence, from Proposition 3.14, D∪{x}D\cup\{x\} is an open irredundant set. This means that vertex xx has an external private neighbour with respect to D∪{x}D\cup\{x\}. Thus, there exists a vertex z∈V−(D∪{x})=(V−D)−{x}z \in V-(D\cup\{x\})=(V-D)-\{x\} which is an external private neighbour of xx with respect to D∪{x}D\cup\{x\}. In particular, vertex zz has no neighbours in DD, which contradicts the fact that DD is a γ\gamma-set of GG. Thus, V−DV-D is a minimal super dominating set of GG. □

Now we can generalize Proposition 3.1.

Proposition 3.6. For any graph GG of order nn, γ(G)+Γsp(G)≥n\gamma(G)+\Gamma_{sp}(G)\ge n.

Proof. Let DD be a γ\gamma-set in a graph GG such that DD is open irredundant (from Theorem 3.4 we know that such a γ\gamma-set exists). By Lemma 3.5, V−DV-D is a minimal super dominating set, so ∣V−D∣≤Γsp(G)|V-D|\le\Gamma_{sp}(G). Thus, we have that n−γ(G)≤Γsp(G)n-\gamma(G)\le\Gamma_{sp}(G), or equivalently, Γsp(G)+γ(G)≥n\Gamma_{sp}(G)+\gamma(G)\ge n. ■

Now we give some conditions that guarantee the equality in the inequality of Proposition 3.6.

Proposition 3.7. If there exists a Γsp\Gamma_{sp}-set of GG that is also a minimal dominating set of GG, then γ(G)+Γsp(G)=n\gamma(G)+\Gamma_{sp}(G)=n.

Proof. Let GG be a graph having a Γsp\Gamma_{sp}-set DD that is also a minimal dominating set of GG. From Proposition 3.6 we have that γ(G)+Γsp(G)≥n\gamma(G)+\Gamma_{sp}(G)\ge n. From Observation 3.15, V−DV-D is an open irredundant set. In [18] Ore proved that the complement of a minimal dominating set is a dominating set, so V−DV-D is also a dominating set. Thus, ∣V−D∣≥γ(G)|V-D|\ge\gamma(G), so n−Γsp(G)≥γ(G)n-\Gamma_{sp}(G)\ge\gamma(G). Thus, γ(G)+Γsp(G)≤n\gamma(G)+\Gamma_{sp}(G)\le n, and finally, γ(G)+Γsp(G)=n\gamma(G)+\Gamma_{sp}(G)=n. ■

Corollary 3.8. If there exists a Γsp\Gamma_{sp}-set DD in a graph GG that is a dominating set and its complement V−DV-D is also a dominating set, then γ(G)+Γsp(G)=n\gamma(G)+\Gamma_{sp}(G)=n.

Observation 3.9. If a graph GG has a universal vertex, then γ(G)=1\gamma(G)=1, Γsp(G)=n−1\Gamma_{sp}(G)=n-1, and γ(G)+Γsp(G)=n\gamma(G)+\Gamma_{sp}(G)=n.

In [9], the authors give a characterization of graphs GG such that γsp(G)=n−1,γ(G)=1\gamma_{sp}(G)=n-1,\gamma(G)=1, which satisfy the observation below.

Super domination and enclaveless parameters

In 1977 Slater [21] defined an enclave in a set S⊆VS \subseteq V to be a vertex v∈Sv \in S such that N[v]⊆SN[v] \subseteq S, that is, vv and all of its neighbours are in SS. A set SS is enclaveless if it contains no enclaves. One can observe that a set SS is a dominating set of a graph GG if and only if its complement V−SV-S is enclaveless. The maximum cardinality of an enclaveless set in a graph GG is denoted by Ψ(G)\Psi(G) and is called the enclaveless number of GG, while the lower enclaveless number ψ(G)\psi(G) equals the minimum cardinality of a maximal enclaveless set. In [21] Slater established the following result.

Theorem 3.10. ([21]) For any graph GG of order nn, γ(G)+Ψ(G)=n\gamma(G) + \Psi(G) = n.

The simple proof of this theorem immediately yields the following two corollaries.

Corollary 3.11. For any graph GG, the complement of any (minimal) dominating set is a (maximal) enclaveless set, and the complement of any (maximal) enclaveless set is a (minimal) dominating set.

Corollary 3.12. For any graph GG of order nn, Γ(G)+ψ(G)=n\Gamma(G) + \psi(G) = n.

Thus, from Proposition 3.6 and Theorem 3.10, we have the following inequality.

Proposition 3.13. For any graph GG, Γsp(G)≥Ψ(G)\Gamma_{sp}(G) \geq\Psi(G).

Super domination and open irredundance parameters

We begin with relations between open irredundant and super dominating sets.

Proposition 3.14. S⊆VS \subseteq V is an open irredundant set of GG if and only if the set V−SV-S is a super dominating set of GG.

Proof. A set SS is an open irredundant set of GG if and only if every vertex u∈Su \in S has an external private neighbour with respect to SS. This implies that V−SV-S dominates the set SS and for every vertex u∈V−Su \in V-S there is a vertex v∈V−(V−S)=Sv \in V-(V-S)=S whose only neighbor in V−SV-S is uu, and thus V−SV-S is a super dominating set of GG. ■\blacksquare

In addition, the following is true.

Observation 3.15. If S⊆VS \subseteq V is a super dominating set of GG, then V−SV-S is an open irredundant set, but not necessarily a dominating set.

For example, any four consecutive vertices of a cycle C6C_6 form a (minimal) super dominating set whose complement fails to dominate C6C_6.

As a consequence of Proposition 3.14 we can relate minimal super dominating sets of GG with maximal open irredundant sets of GG.

Proposition 3.16. A set S⊆VS \subseteq V is a maximal open irredundant set of GG if and only if V−SV-S is a minimal super dominating set of GG.

Proof. Let SS be a maximal open irredundant set. From Proposition 3.14 it follows that V−SV-S is a super dominating set of GG. Assume that V−SV-S is not a minimal super dominating set. Then there exists a super dominating set T⊂V−ST \subset V-S. By Proposition 3.14 we know that V−TV-T is an open irredundant set, but S⊂V−TS \subset V-T, which contradicts the assumption that SS is a maximal open irredundant set of GG. Thus, V−SV-S is a minimal super dominating set.

Conversely, let DD be a minimal super dominating set of GG. From Proposition 3.14, V−DV-D is an open irredundant set. Assume that V−DV-D is not a maximal open irredundant set. Then there exists an open irredundant set FF such that V−D⊂FV-D \subset F. By Proposition 3.14 we know that V−FV-F is a super dominating set of GG. But V−F⊂DV-F \subset D, which contradicts the fact that DD is a minimal super dominating set of GG. Thus, V−DV-D is a maximal open irredundant set. ■

Recall from the Introduction that oir(G)oir(G) and OIR(G)OIR(G) equal the minimum and maximum cardinality of a maximal open irredundant set, respectively. In this section we establish two Gallai theorems involving super domination and open irredundance.

Theorem 3.17. For any graph GG of order nn, γsp(G)+OIR(G)=n\gamma_{sp}(G) + OIR(G) = n.

Proof. Let DD be a minimum cardinality super dominating set of a graph GG, so that ∣D∣=γsp(G)|D| = \gamma_{sp}(G). Then ∣D∣≤∣S∣|D| \le|S| for every super dominating set SS of GG. So, −∣D∣≥−∣S∣-|D| \ge-|S| for every super dominating set SS of GG and therefore, ∣V−D∣=n−∣D∣≥n−∣S∣=∣V−S∣|V-D| = n-|D| \ge n-|S| = |V-S| for every super dominating set SS of GG. By Proposition 3.14, this is equivalent to the fact that ∣V−D∣=n−∣D∣≥∣T∣|V-D| = n-|D| \ge|T| for every open irredundant set TT of GG. Then V−DV-D is an open irredundant set of GG of maximal cardinality, so ∣V−D∣=OIR(G)|V-D| = OIR(G). Therefore, n=∣D∣+∣V−D∣=γsp(G)+OIR(G)n = |D| + |V-D| = \gamma_{sp}(G) + OIR(G). ■

Theorem 3.18. For any graph GG of order nn, Γsp(G)+oir(G)=n\Gamma_{sp}(G) + oir(G) = n.

Proof. Let DD be a minimal super dominating set in a graph GG of maximum cardinality, so that D=Γsp(G)D = \Gamma_{sp}(G). Then ∣D∣≥∣S∣|D| \ge|S| for every minimal super dominating set SS of GG, so −∣D∣≤−∣S∣-|D| \le-|S|, for every minimal super dominating set SS of GG. Therefore, ∣V−D∣=n−∣D∣≤n−∣S∣=∣V−S∣|V-D| = n-|D| \le n-|S| = |V-S| for every minimal super dominating set SS of GG. By Proposition 3.16 this implies that ∣V−D∣=n−∣D∣≤∣T∣|V-D| = n-|D| \le|T| for every maximal open irredundant set TT of GG. Therefore, V−DV-D is a maximal open irredundant set of GG of minimum cardinality, and so, ∣V−D∣=oir(G)|V-D| = oir(G). Thus, n=∣D∣+∣V−D∣=Γsp(G)+oir(G)n = |D| + |V-D| = \Gamma_{sp}(G) + oir(G). ■

From Theorem 3.17, Theorem 3.18, and Proposition 2.1, we can conclude that the difference OIR(G)−oir(G)OIR(G)-oir(G) can be arbitrarily large.

Corollary 3.19. For any positive integer k∈Nk \in\mathbb{N} there exists a graph GG such that OIR(G)−oir(G)=kOIR(G)-oir(G) = k.

Aknowledgements

We would like to express our sincere thanks to Professor Stephen Hedetniemi for his kind support and for the inspiration to write this article.

References

  1. [1]S. Balasubramanian, J. Farr, K. Bernasconi, R. Laskar, J. Villalpando, K. Hutson, G. Stevens, M. Gairing, S.T. Hedetniemi, Gallai theorems involving domination parameters. Congr. Numer. 157 (2002), 149–157.
  2. [2]B. Bollobás, E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance. J. Graph Theory 3 (1979), 241–249.DOI
  3. [3]C. Bujtás, N. Ghanbari, S. Klavžar, Computational complexity aspects of super domination. Theoret. Comput. Sci. 975 (2023), Paper No. 114137, 14 pp.arxiv.org/abs/2302.08862
  4. [4]A. Cabrera-Martínez, A. Conchado Peiró, Relating the super domination and 2-domination numbers in cactus graphs. Open Math. 21 (2023), no.1, Paper No. 20220583, 8 pp.DOI
  5. [5]E.J. Cockayne, Nordhaus-Gaddum results for open irredundance. J. Comb. Math. Comb. Comput. 47 (2003), 213–22.
  6. [6]E.J. Cockayne, O. Favaron, S. Finbow, C.M. Mynhardt, Open irredundance and maximum degree in graphs. Discrete Math. 308 (2008), no. 23, 5358–5375.DOI
  7. [7]E.J. Cockayne, S. Finbow, Generalized irredundance in graphs: Nordhaus-Gaddum bounds. Discuss. Math. Graph Theory 24 (2004), no. 1, 147–160.DOI
  8. [8]E.J. Cockayne, S.T. Hedetniemi, R. Laskar, Gallai theorems for graphs, hypergraphs, and set systems. Discrete Math. 72 (1988), 35–47.
  9. [9]M. Dettlaff, M. Lemańska, J.A. Rodríguez-Velázquez, R. Zuazua, On the super domination number of lexicographic product graphs. Discrete Appl. Math. 263 (2019), 118–129.arxiv.org/abs/1703.06034
  10. [10]A.M. Farley, A. Proskurovski, Computing the maximum order of an open irredundant set in a tree. Congr. Numer. 41 (1984), 219–228.
  11. [11]A.M. Farley, N. Schachum, Senders in broadcast networks: open irredundancy in graphs. Congr. Numer. 38 (1983), 47–57.
  12. [12]T. Gallai, Über extreme Punkt-und Kantenmengen. Ann. Univ. Sci., Budapest, Eötvös Sect. Math. 2 (1959), 133–138.
  13. [13]N. Ghanbari, Some results on the super domination number of a graph. Discrete Math. Algorithms Appl. 16 (2024), no. 4, Paper No. 2350044, 12 pp.arxiv.org/abs/2204.10666
  14. [14]N. Ghanbari, G. Jäger, T. Lehtilä, Super domination: graph classes, products and enumeration. Discrete Appl. Math.349 (2024), 8–24.arxiv.org/abs/2209.01795
  15. [15]D.J. Klein, J.A. Rodríguez-Velázquez, E. Yi, On the super domination number of graphs. Comm. Combin. Optim. 5 (2020), no. 2, 83–96.
  16. [16]B. Krishnamurti, Y.B. Venkatakrishnan, Double domination and super domination in trees. Discrete Math. Algorithms Appl. 8 (2016), Paper No. 1650067, DOI: https://doi.org/10.1142/S1793830916500671.
  17. [17]M. Lemańska, V. Swaminathan, Y.B. Venkatakrishnan, R. Zuazua, Super dominating sets in graphs. Proc. Nat. Acad. Sci. India Sect. A 85 (2015), no. 3, 353–357.arxiv.org/abs/1309.1315
  18. [18]O. Ore, Theory of Graphs. Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc., Providence, 1962), 206–212.
  19. [19]J.A. Rodríguez-Velázquez, D.J. Klein, E. Yi, On the super domination number of graphs, Comm. Comb. Optim. 5 (2020), 83–96, DOI: https://doi.org/10.22049/cco.2019.26587.1122.
  20. [20]B. Senthilkumar, Y.B. Venkatakrishnan, H. Naresh Kumar, Super domination in trees. Discrete Math. Algorithms Appl. 14 (2022), Paper No. 2150137, DOI: https://doi.org/10.1142/S1793830921501378.
  21. [21]P.J. Slater, Enclaveless sets and MK-systems. J. Res. Nat. Bur. Standards 82 (1977), no. 3, 197–202.DOI
  22. [22]W. Zhuang, Super domination in trees. Graphs Comb. 38 (2022), 21, DOI: https://doi.org/10.1007/s00373-021-02409-3.

Paper details

vlnc:W_rwtaj28e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents