WorksMathematics
Minimal super dominating sets of maximum cardinality
Abstract
Let be a graph. A subset of vertices is a super dominating set if every vertex has a neighbour , whose only neighbour in is . A set is called open irredundant if every vertex has at least one neighbour whose only neighbour in is . 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 as the maximum cardinality of a minimal super dominating set of and calculate for some families of graphs . 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 a simple graph. A set vertex set is called independent if no two vertices in are adjacent. The vertex independence number equals the maximum cardinality of an independent set of . A set is called a vertex cover if for every edge , either , or , or both and , are in . The vertex covering number equals the minimum cardinality of a vertex cover of . In 1959 Gallai [12] observed that a set is a maximal independent set if and only if the complement is a minimal vertex cover. From this it is straightforward to prove the following theorem.
Theorem 1.1. (Gallai [12]) For any graph of order , .
Since 1959 many theorems of the form have been proven, where and 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 of a vertex in a graph is the set of vertices which are adjacent to . The closed neighbourhood is the set . The open (closed) neighbourhood () of a set of vertices is the union of the open (closed) neighbourhoods () of vertices . For a set of vertices, we say that a vertex has an external private neighbour with respect to if .
In this paper we are interested in the following three types of set of vertices in a graph.
A set of vertices is a dominating set if , or equivalently, if every vertex has at least one neighbour in . The domination number of a graph equals the minimum cardinality of a dominating set of . A dominating set of with minimum cardinality is called a -set of .
A set is called a super dominating set of if every vertex has an external private neighbour , with respect to . The super domination number equals the minimum cardinality of a super dominating set in a graph . A super dominating set of with minimum cardinality is called a -set of .
A set is called a open irredundant set of if every vertex has an external private neighbour with respect to . The open irredundance number equals the minimum cardinality of a maximal open irredundant set of . An open irredundant set of with minimum cardinality is called an -set of . 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 and we define the new parameter as the maximum cardinality of a minimal super dominating set of . We calculate for some families of graphs . 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 is a super dominating set of if for every vertex , there exists a vertex such that . In the other words, is a super dominating set if every vertex has an external private neighbour , with respect to . The super domination number equals the minimum cardinality of a super dominating set in a graph . 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 with order , . In Theorem 2.1, they give a characterization for connected graph with . Moreover, in section 3, they show a characterization of trees which attain the lower and the upper bounds in terms of .
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 as the maximum cardinality of a minimal super dominating set of and a minimal superdominating set of with maximum cardinality we call a -set of . By definition, for any graph , .
In the next proposition we show that the difference between and can be arbitrarily large.
Proposition 2.1. For any there exists a graph such that .
Proof. Consider a graph from Figure 1. On the left side there is with depicted in black vertices belonging to a -set and in the left side with depicted in black vertices belonging to a -set. ▪

Figure 1. Graph for which .
We now determine the upper super domination number of the path on vertices. We begin with determining this parameter for the first 21 paths. The following table show the exact value of for .
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| 1 | 2 | 2 | 3 | 4 | 5 | 5 | 6 | 7 | 7 | |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
| 8 | 9 | 10 | 10 | 11 | 12 | 12 | 13 | 14 | 15 |
Table 1. Exact values of for .
The vertices on the picture below on the left side of the paths form a minimal super dominating sets of maximum cardinality.

Figure 3.
For , let be a path with set of vertices and set of edges . For with , we will denote the subset by .
Observation 2.2. Let , . For every minimal super dominating set of , .
Proof. If , then would be a super dominating set of contradicting that is minimal.
Observation 2.3. Let , . For every minimal superdominating set of and every , .
Proof. If , then would be a super dominating set of contradicting that is minimal.
Observation 2.4. Let , . For every minimal superdominating set of , .
Proof. By Observation 2.3, . Suppose , by Observation 2.2, , and by Observation 2.3, . If , then would be a superdominating set of contradicting that is minimal, and if , then would be a super dominating set of contradicting that is minimal.
Lemma 2.5. Let , . For every minimal superdominating set of and every , .
Proof. Suppose , then would be a super dominating set of contradicting that is minimal.
Now, suppose , by Lemma 2.3, none five consecutive vertices belong to , so , if or , then would be a super dominating set of , and if , then would be a super dominating set of , contradicting in both cases that is minimal.
Proposition 2.6. Let . Let such that , with . Then .
Proof. Let be a minimal super dominating set of . We consider some cases, depending from the value of .
Case 1: . By Lemma 2.5, every , , then
For the remaining cases, we see that if the result is clear, because , , , and all those values are less or equal to . Suppose now .
Case 2: . By Lemma 2.5, for every , , then
Case 3: . By Lemma 2.5, for every , , then
Case 4: . By Lemma 2.5, for every , , and by Observation 2.2, , then
Case 5: . By Lemma 2.5, for every , , and by Observation 2.2, , then
Case 6: . By Lemma 2.5, for every , , and by Observation 2.3, , then
Case 7: . By Lemma 2.5, for every , , and by Observation 2.4, , then
In all cases .
Proposition 2.7. Let , . Let such that , with . Then if , and if .
Proof. For each let and if .
If or , then the set is a minimal super dominating set of with . Then, .
For define:
if , ,
if and , ,
if , ,
if and , .
The set is a minimal super dominating set of with . Then, .
Theorem 2.8. Let . Let such that , with and such that , with . Then or .
Proof. We consider some cases, depending on the values of . The cases are immediate, so we may assume that .
Case 1: . In this case , with , and , with . As with , by Proposition 2.6, , and by Proposition 2.7, . Then, .
Case 2: . In this case , with , and , with and . As with , by Proposition 2.6, , and by Proposition 2.7, , and . Then, or .
Case 3: . As , with and such that , with , then , so by Proposition 2.6,
Now, by Proposition 2.7,
but, and , so . Then, (when and , or when and ), or in the remaining cases, so
or
We conclude that or .
By the analysis made in the proof of Theorem 2.8, we have the following
Corollary 2.9. Let . Let such that , with and such that , with . In the following cases:
(a) , or
(b) , and , or
(c) , and ,
we have that .
Now we consider the case of cycles. For , let be the cycle with set of vertices and set of edges .
Lemma 2.10. Let , . For every minimal super dominating set of , there exist two adjacent vertices of such that .
Proof. Let be a minimal super dominating set of . Consider ; as is a super dominating set, has an external private neighbour with respect to . Then, as is an external private neighbour with respect to , is in . ■
Lemma 2.11. Let be a -set and let be adjacent vertices in . Then any longest path in with and has a length satisfying .
Proof. Suppose by contradiction that has length more than three; then there exists a path contained in . But in that case is a super dominating set of with cardinality , a contradiction with minimality of . Thus with . ■
Proposition 2.12. For every integer , we have .
Proof. Let be a -set and consider two vertices adjacent in . Let be a longest path with and ; from Lemma 2.11 .
If , then is a minimal super dominating set of , where ;
If and , then is a minimal super dominating set of , where ;
If and , then is a minimal super dominating set of , where .
Then, . ■
Finally, we consider minimal super dominating sets of maximum cardinality in caterpillars. For with , let be a caterpillar graph with set of vertices and set of edges . Notice that .
Lemma 2.13. Let with . For every minimal super dominating set of , .
Proof. As must be dominated by , then . Suppose by contradiction that , then, as is not a super dominating set, would not have a private neighbour with respect to , so , but this implies, as must be dominated by , . Then would be a super dominating set, which is a contradiction.
We conclude . Similarly, . ■
Lemma 2.14. Let with . For every minimal super dominating set of and for every , .
Proof. Suppose by contradiction that . By Lemma 2.13, and . As is not a super dominating set, . Also, as is not a super dominating set, . As consequence, , otherwise they would not have a private neighbour with respect to . Then, would be a super dominating set, which is a contradiction.
We conclude .
Theorem 2.15. Let . Then,
Proof. First we will prove that
We consider some cases, depending on the value of . Minimal super dominating sets of maximum cardinality of are marked on Figure 2 (PDF p. 9).
Figure 2 (PDF p. 9). Minimal super dominating sets of maximum cardinality of
Case 1: , with .
For the set
is a minimal super dominating set of , so .
For , the set
is a minimal super dominating set of , so .
Case 2: , with .
(a) For , the set
is a minimal super dominating set of , so .
(b) For , the set
is a minimal super dominating set of , so .
Now, we will prove that
Let be a minimal super dominating set of . Similarly like before, we consider some cases depending on the value of . Case 1: , with . Using Lemma 2.13 and Lemma 2.14 we have that
Case 2: , with . Using Lemma 2.13 and Lemma 2.14 we have
We conclude
Some Gallai-type theorems
In this section we present some Gallai-type theorems involving dominating, super dominating and open irredundant sets.
Relations between and
The calculations we showed in the previous section lead us to the following two propositions.
Proposition 3.1. Let . Then, .
Proof. Let such that , with . For , we have the equality . For , we know that and by Proposition 2.7 so,
We consider some cases, depending on the value of .
Case 1: , .
Case 2: , .
Case 3: , .
We conclude that .
Observation 3.2. Notice that there exist such that , for example , with , and .
The following proposition shows the strict inequality fulfill for caterpillars:
Proposition 3.3. Let with . Then, .
Proof. Let with . Consider the following cases:
Case1: , with . By Proposition 2.15, . Also, is a dominating set of of minimum cardinality, so . Then,
Case 2: , with . By Proposition 2.15, . Also, is a dominating set of of minimum cardinality, so . Then,
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 contains an open irredundant -set, that is a minimum cardinality dominating set in which every vertex 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 and the upper super domination number .
Lemma 3.5. If is a -set in a graph that is open irredundant, then is a minimal super dominating set of .
Proof. Let be a -set in a graph that is open irredundant. Thus, is a private dominating set and from Proposition 3.14, we have that is a super dominating set. Assume that is not a minimal super dominating set; thus there exists a vertex such that is a super dominating set. Hence, from Proposition 3.14, is an open irredundant set. This means that vertex has an external private neighbour with respect to . Thus, there exists a vertex which is an external private neighbour of with respect to . In particular, vertex has no neighbours in , which contradicts the fact that is a -set of . Thus, is a minimal super dominating set of . □
Now we can generalize Proposition 3.1.
Proposition 3.6. For any graph of order , .
Proof. Let be a -set in a graph such that is open irredundant (from Theorem 3.4 we know that such a -set exists). By Lemma 3.5, is a minimal super dominating set, so . Thus, we have that , or equivalently, . ■
Now we give some conditions that guarantee the equality in the inequality of Proposition 3.6.
Proposition 3.7. If there exists a -set of that is also a minimal dominating set of , then .
Proof. Let be a graph having a -set that is also a minimal dominating set of . From Proposition 3.6 we have that . From Observation 3.15, is an open irredundant set. In [18] Ore proved that the complement of a minimal dominating set is a dominating set, so is also a dominating set. Thus, , so . Thus, , and finally, . ■
Corollary 3.8. If there exists a -set in a graph that is a dominating set and its complement is also a dominating set, then .
Observation 3.9. If a graph has a universal vertex, then , , and .
In [9], the authors give a characterization of graphs such that , which satisfy the observation below.
Super domination and enclaveless parameters
In 1977 Slater [21] defined an enclave in a set to be a vertex such that , that is, and all of its neighbours are in . A set is enclaveless if it contains no enclaves. One can observe that a set is a dominating set of a graph if and only if its complement is enclaveless. The maximum cardinality of an enclaveless set in a graph is denoted by and is called the enclaveless number of , while the lower enclaveless number equals the minimum cardinality of a maximal enclaveless set. In [21] Slater established the following result.
Theorem 3.10. ([21]) For any graph of order , .
The simple proof of this theorem immediately yields the following two corollaries.
Corollary 3.11. For any graph , 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 of order , .
Thus, from Proposition 3.6 and Theorem 3.10, we have the following inequality.
Proposition 3.13. For any graph , .
Super domination and open irredundance parameters
We begin with relations between open irredundant and super dominating sets.
Proposition 3.14. is an open irredundant set of if and only if the set is a super dominating set of .
Proof. A set is an open irredundant set of if and only if every vertex has an external private neighbour with respect to . This implies that dominates the set and for every vertex there is a vertex whose only neighbor in is , and thus is a super dominating set of .
In addition, the following is true.
Observation 3.15. If is a super dominating set of , then is an open irredundant set, but not necessarily a dominating set.
For example, any four consecutive vertices of a cycle form a (minimal) super dominating set whose complement fails to dominate .
As a consequence of Proposition 3.14 we can relate minimal super dominating sets of with maximal open irredundant sets of .
Proposition 3.16. A set is a maximal open irredundant set of if and only if is a minimal super dominating set of .
Proof. Let be a maximal open irredundant set. From Proposition 3.14 it follows that is a super dominating set of . Assume that is not a minimal super dominating set. Then there exists a super dominating set . By Proposition 3.14 we know that is an open irredundant set, but , which contradicts the assumption that is a maximal open irredundant set of . Thus, is a minimal super dominating set.
Conversely, let be a minimal super dominating set of . From Proposition 3.14, is an open irredundant set. Assume that is not a maximal open irredundant set. Then there exists an open irredundant set such that . By Proposition 3.14 we know that is a super dominating set of . But , which contradicts the fact that is a minimal super dominating set of . Thus, is a maximal open irredundant set. ■
Recall from the Introduction that and 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 of order , .
Proof. Let be a minimum cardinality super dominating set of a graph , so that . Then for every super dominating set of . So, for every super dominating set of and therefore, for every super dominating set of . By Proposition 3.14, this is equivalent to the fact that for every open irredundant set of . Then is an open irredundant set of of maximal cardinality, so . Therefore, . ■
Theorem 3.18. For any graph of order , .
Proof. Let be a minimal super dominating set in a graph of maximum cardinality, so that . Then for every minimal super dominating set of , so , for every minimal super dominating set of . Therefore, for every minimal super dominating set of . By Proposition 3.16 this implies that for every maximal open irredundant set of . Therefore, is a maximal open irredundant set of of minimum cardinality, and so, . Thus, . ■
From Theorem 3.17, Theorem 3.18, and Proposition 2.1, we can conclude that the difference can be arbitrarily large.
Corollary 3.19. For any positive integer there exists a graph such that .
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]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]B. Bollobás, E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance. J. Graph Theory 3 (1979), 241–249.DOI
- [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]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]E.J. Cockayne, Nordhaus-Gaddum results for open irredundance. J. Comb. Math. Comb. Comput. 47 (2003), 213–22.
- [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]E.J. Cockayne, S. Finbow, Generalized irredundance in graphs: Nordhaus-Gaddum bounds. Discuss. Math. Graph Theory 24 (2004), no. 1, 147–160.DOI
- [8]E.J. Cockayne, S.T. Hedetniemi, R. Laskar, Gallai theorems for graphs, hypergraphs, and set systems. Discrete Math. 72 (1988), 35–47.
- [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]A.M. Farley, A. Proskurovski, Computing the maximum order of an open irredundant set in a tree. Congr. Numer. 41 (1984), 219–228.
- [11]A.M. Farley, N. Schachum, Senders in broadcast networks: open irredundancy in graphs. Congr. Numer. 38 (1983), 47–57.
- [12]T. Gallai, Über extreme Punkt-und Kantenmengen. Ann. Univ. Sci., Budapest, Eötvös Sect. Math. 2 (1959), 133–138.
- [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]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]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]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]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]O. Ore, Theory of Graphs. Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc., Providence, 1962), 206–212.
- [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]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]P.J. Slater, Enclaveless sets and MK-systems. J. Res. Nat. Bur. Standards 82 (1977), no. 3, 197–202.DOI
- [22]W. Zhuang, Super domination in trees. Graphs Comb. 38 (2022), 21, DOI: https://doi.org/10.1007/s00373-021-02409-3.
