A new look at the concept of domination in hypergraphs

P.M. Divya^a , T.V. Ramakrishnan^b , S. Arumugam^c

divyapmadhavan@gmail.com, ramakrishnantvknr@gmail.com, s.arumugam@ritrjpm.ac.in

In this paper we propose a new definition of domination in hypergraphs in such a way that when restricted to graphs it is the usual domination in graphs. Let H = (V, E) be a hypergraph. A subset S of V is called a dominating set of H if for every vertex v in V − S, there exists an edge e ∈ E such that v ∈ e and e − {v} ⊆ S. The minimum cardinality of a dominating set of H is called the domination number of H and is denoted by γ(H). We determine the domination number for several classes of uniform hypergraphs.We characterise minimal dominating sets and introduce the concept of independence and irredundance leading to domination chain in hypergraphs.

Keywords: hypergraph, domination, independence. Mathematics Subject Classification : 05C22

DOI: 10.5614/ejgta.2024.12.2.3

1. Introduction

By a graph G = (V, E) we mean a finite undirected graph with neither loops nor multiple edges. For graph theoretic terminology we refer to Chartrand and Lesniak [1]. For terminology in hypergraphs we refer to Berge [2, 3].

Received: 22 November 2020, Revised: 18 January 2022, Accepted: 13 May 2024.

^aDepartment of Mathematics, S.N. College, Kanuur

^bDepartment of Mathematics, Kannur University, Kannur, Kerala

^cAdjunct Professor, Department of Computer Science and Engineering Ramco Institute of Technology, Rajapalayam-626 117, Tamil Nadu, India.

A hypergraph H is an ordered pair (V, E) where V is a finite nonempty set and E is a subset of the power set P(V ) such that |e| ≥ 2 for all e ∈ E and S e∈E e = V. A hypergraph H is called a simple hypergraph if no edge is a proper subset of another edge. Two vertices u, v ∈ V are called adjacent if there exists an edge e ∈ E such that {u, v} ⊆ e. Throughout this paper we consider only simple hypergraphs. A hypergraph H is called a k-uniform hypergraph if |e| = k for all e ∈ E. If E = {e : e ⊆ V and |e| = k}, then H is called a complete k-uniform hypergraph. Let H = (V, E) be a hypergraph. A hypergraph H¹ = (V1, E1) is called a subhypergraph of H if V¹ ⊆ V and E¹ ⊆ E.

Domination in graphs has been extensively investigated. An excellent treatment of fundamentals of domination is given in [4]. For survey of several advanced topics in domination we refer to [5]. For recent results on domination related parameters we refer to [11, 12]. Let G = (V, E) be a graph. A subset D ⊆ V is called a dominating set of G if for every vertex v in V − D, there exists u ∈ D such that u and v are ajdacent. The domination number γ(G) of G is the minimum cardinality of a dominating set of G.

Theorem 1.1. [4] If G is a path Pⁿ or a cycle Cⁿ of order n, then γ(G) = n 3 .

Definition 1.1. [4] Let P denote a graph theoretic property of a set of vertices S in a graph G = (V, E). If S has property P, then S is called a P-set; otherwise it is a P-set. A property P is said to be hereditary if every subset of a P-set is a P-set. A P-set S is called a maximal P-set if every proper superset T ⊃ S is a P-set. A P-set S is a 1-maximal P-set if S ∪ {v} is a P-set for every v ∈ V − S.

Theorem 1.2. [4] Let G = (V, E) be a graph and let P be a hereditary property. Then a set S is a maximal P-set if and only if S is a 1-maximal P-set.

One can similarly define superhereditary property P, minimal P-set, 1-minimal P-set and obtain a theorem analogous to Theorem 1.3. For further details we refer to ([4], Page 67-68).

The concept of domination in graphs can be looked at from three different perspectives. Let D ⊆ V (G) and let v ∈ V − D. Then D is a dominating set of G if and only if one of the following holds.

• (i) There exists a vertex u ∈ D such that uv is an edge of G.
• (ii) There exists an edge e ∈ E such that v ∈ e and e − {v} ⊆ D.
• (iii) There exists an edge e ∈ E such that v ∈ e and |D ∩ e| ≥ l |e| 2 m .

Acharya [6] introduced the concept of domination in hypergraphs using (i).

Definition 1.2. [6] Let H = (V, E) be a hypergraph. A subset D of V is called a dominating set of H if for every v ∈ V − D, there exists u ∈ D such that u and v are adjacent.

Further results on domination in hypergraphs are given in [8, 7, 9].

According to the above definition an edge e of a hypergraph H is considered as a complete graph so that any vertex v of e dominates all the remaining vertices of e, irrespective of the cardinality |e|. In fact if G is the graph with V (G) = V (H) and the subgraph of G induced by the set

of all vertices of any edge e is \(K_{|e|}\), then the domination in H is equivalent to domination in the graph G.

In this paper we propose a new definition for domination in hypergraphs which is formulated using (ii), so that this coincides with the usual concept of domination when restricted to graphs.

2. Main Results

We start with a new look at the concept of domination in hypergraphs.

Definition 2.1. Let \(H=(V,\mathcal{E})\) be a hypergraph. A subset D of V is called a dominating set of H if for every \(v \in V-D\), there exists an edge \(e \in \mathcal{E}\) such that \(v \in e\) and \(e-\{v\} \subseteq D\). The minimum cardinality of a dominating set of H is called the domination number of H and is denoted by \(\gamma(H)\).

We observe that when restricted to graphs, this coincides with the usual concept of domination in graphs.

Also according to Definition 1.4 an edge e of a hypergraph dominates |e|-1 vertices in V-D whereas according to Definition 2.1, e dominates just one vertex in V-D. Hence the domination number obtained by using Definition 2.1 may be much larger than the domination number obtained from Definition 1.4.

Example 2.1.

• (i) For the complete r-uniform hypergraph \(K_n^r\), we have \(\gamma(K_n^r) = r 1\).
• (ii) The complete r-partite r-uniform hypergraph \(H=(V,\mathcal{E})\) is such that V can be partitioned into r nonempty subsets \(V_1,V_2,\ldots,V_r\) and \(\mathcal{E}=\{e\subseteq V:|e|=r \text{ and }|e\cap V_i|=1 \text{ for each }i\}\). If \(|V_i|=n_i\), we denote this hypergraph by \(H=K^r_{n_1,n_2,\ldots,n_r}\). Clearly If \(D\subseteq V,|D|=r-1\) and \(|D\cap V_i|=1\) for all \(i,1\leq i\leq r-1\), then D is a minimum dominating set of H. Hence \(\gamma(H)=r-1\). In particular consider \(|H=K^3_{2,2,3}\) where the partite sets are \(V_1=\{a_1,a_2\},V_2=\{b_1,b_2\}\) and \(V_3=\{c_1,c_2,c_3\}\). Let \(D=\{a_1,b_1\}\). Since \(e=\{a_1,b_1,c_1\}\) is an edge in H, it follows that \(c_1\) is dominated by D. Similarly D dominates all the vertices of H.

Definition 2.2. A vertex v of a hypergraph H is called a pendent vertex if \(v \in e\) for exactly one edge e of H.

The r-uniform linear path \(P_m^r\) is the hypergraph H = (V, E) where \(V = \{v_i : 1 \le i \le m(r-1)+1\}, \mathcal{E} = \{e_1, e_2, \dots, e_m\}\) and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

Theorem 2.1. Let \(H = P_m^r\) be the r-uniform linear path. Then

\[\gamma(H) = \begin{cases} \left\lceil \frac{m+1}{3} \right\rceil, & \text{if } r = 2, \\ m(r-2) + 1, & \text{if } r \ge 3. \end{cases}\]

Proof. If r=2, then H is the path \(P_{m+1}\) and hence by Theorem 1.1, \(\gamma(H)=\gamma(P_{m+1})=\left\lceil\frac{m+1}{3}\right\rceil\). Suppose \(r\geq 3\). The vertices \(v_1,v_2,v_3,\ldots,v_{r-1}\) lie only on edge \(e_1\) and hence are pendent vertices. The vertices \(v_{r+1},v_{r+2},\ldots,v_{r-2}\) lie only on the edge \(e_2\) and hence are pendent vertices. In general, all the vertices of \(e_i-\{v_{(i-1)r-(i-2)},v_{ir-(i-1)}\}\) are pendent vertices and hence each edge of H has at least r-2 pendent vertices. Now, choose a pendent vertex \(w_i\) in \(e_i\) where \(1\leq i\leq m\). Then \(D=V-\{w_i:1\leq i\leq m\}\) is a dominating set of H and |D|=|V|-m=m(r-2)+1. Hence \(\gamma(H)\leq m(r-2)+1\). Now let S be any dominating set of H. Since each edge of H has at least r-2 pendent vertices, it follows that at most one pendent vertex of any edge is not in S. Hence \(|S|\geq |V|-m=m(r-2)+1\).

Thus \[\gamma(H) = m(r-2) + 1\].

The r-uniform linear cycle \(C_m^r\) is the hypergraph \(H=(V,\mathcal{E})\) where \(V=\{v_i: 1\leq i\leq m(r-1)\}, \mathcal{E}=\{e_1,e_2,\ldots,e_m\}\) and

The 7-difform infear cycle \[C_m\] is the hypergraph \(H = (V, C_m)\) and

Theorem 2.2. Let \(H = C_m^r\) be the r-uniform cycle. Then

\[\gamma(H) = \begin{cases} \left\lceil \frac{m}{3} \right\rceil, & \text{if } r = 2, \\ m(r-2), & \text{if } r \ge 3. \end{cases}\]

Proof. If r=2, then H is the cycle \(C_m\) and hence by Theorem 1.2, \(\gamma(H)=\gamma(C_m)=\left\lceil\frac{m}{3}\right\rceil\). Suppose \(r\geq 3\). As in Theorem 2.3, we observe that every edge of H contains r-2 pendent vertices. Now, choose a pendent vertex \(w_i\) in \(e_i\) where \(1\leq i\leq m\). Then \(D=V-\{w_i:1\leq i\leq m\}\) is a dominating set of H and |D|=|V|-m=m(r-2). Hence \(\gamma(H)\leq m(r-2)\). Now, let S be any dominating of H. Since each edge of H has exactly R0 pendent vertices, it follows at most pendent vertex of any edge is not in R1. Hence \(|S|\geq |V|-m=m(r-2)\)1. Thus R2 and so R3 and so R4 is the cycle R5.

Let \(H=(V,\mathcal{E})\) be a hypergraph and let \(k=\min_{e\in\mathcal{E}}|e|\). Since \(|e|\geq 2\) for all \(e\in\mathcal{E}\), we have \(k\geq 2\). In the following theorem we prove that k-1 is a lower bound for \(\gamma(H)\). We also determine all hypergraphs for which \(\gamma(H)=k-1\). For this purpose we define a hypergraph.

Let V be any finite set and let S be a proper nonempty subset of V. Let H(S) denote the hypergraph \((V, \mathcal{E}^*)\) where \(\mathcal{E}^* = \{S \cup \{v\} : v \in V - S\}\).

Theorem 2.3. Let \(H = (V, \mathcal{E})\) be a hypergraph and let \(k = \min_{e \in \mathcal{E}} |e|\) and \(k \ge 2\). Then \(\gamma(H) \ge k-1\) and equality holds if and only if there exists a proper subset S of V such that |S| = k-1 and H(S) is a subhypergraph of H.

Proof. Let S be any dominating set of H and let \(v \in V - S\). Then there exists \(e \in \mathcal{E}\) such that \(v \in e\) and \(e - \{v\} \subseteq S\). Hence \(|S| \ge |e| - 1 \ge k - 1\). Hence \(\gamma(H) \ge k - 1\). Now suppose \(\gamma(H) = k - 1\). Let S be a \(\gamma\)-set of H. Then for any \(v \in V - S\), there exists an edge \(e_v \in \mathcal{E}\) such that \(e_v - \{v\} \subseteq S\). Hence \(e_v \subseteq S \cup \{v\}\) and \(|S \cup \{v\}| = k\). Hence \(e_v = S \cup \{v\}\). Let \(\mathcal{E}^* = \{e_v : v \in V - S\}\). Clearly \(\mathcal{E}(H(S)) = \mathcal{E}^* \subseteq \mathcal{E}(H)\). Hence H(S) is a subhypergraph of H. Conversely if H(S) is a subhypergraph of H, then S is a dominating set of H. Hence \(\gamma(H) \le |S| = k - 1\).

Corollary 2.1. Let H = (V, E) be a hypergraph and let |V | = n. Then γ(H) = 1 if and only if the star K1,n−¹ is a subhypergraph of H.

Since domination in hypergraph is a superhereditary property, it follows from analogus of Theorem 1.3 that a dominating set S of a hypergraph H is a minimal dominating set if and only if S − {v} is not a dominating set of H for all v ∈ S.

In the following theorem we obtain a characterization of minimal dominating sets.

Theorem 2.4. Let S be a dominating set of a hypergraph H = (V, E). Then S is a minimal dominating set of H if and only if for each u ∈ S, one of the following holds.

• (i) If e ∈ E and u ∈ e, then e ∩ (V − S) ̸= ∅.
• (ii) There exists a vertex v ∈ V − S such that if e is any edge in E with v ∈ e and e − {v} ⊆ S, then u ∈ e.

Proof. Let S be a minimal dominating set of H and let u ∈ S. Then S¹ = S − {u} is not a dominating set of H. Hence there exists a vertex v ∈ V − S¹ such that v is not dominated by S1. If v = u then (i) holds.

Suppose u ̸= v. Let e be any edge of H such that v ∈ e and e − {v} ⊆ S. If u ̸∈ e, then v is dominated by S − {u}, which is a contradiction. Hence (ii) holds.

Conversely, suppose that for each u ∈ S, either (i) or (ii) holds. If (i) holds, then u is not dominated by S − {u}. If (ii) holds, then v is not dominated by S − {u}. Hence S − {u} is not a dominating set H and so S is a minimal dominating set of H.

Definition 2.3. Let H = (V, E) be a hypergraph. The maximum cardinality of a minimal dominating set of H is called the upper domination number of H and is denoted by Γ(H).

It follows from the definition that γ(H) ≤ Γ(H).

We now proceed to introduce the concept of independence in hypergraphs.

Definition 2.4. Let H = (V, E) be a hypergraph. A subset S of V is called an independent set if e ̸⊆ S for any e ∈ E.

Example 2.2. Let e ∈ E be any edge of H. Since H is a simple hypergraph, |e| ≥ 2. Clearly S = e − v where v ∈ V is an independent set in H.

Clearly independence in hypergraph is a hereditary property. Hence it follows from Theorem 1.3 that an independent set S is maximal if and only if S ∪ {u} is not an independent set for any u ∈ V − S.

Theorem 2.5. Let H = (V, E) be a hypergraph. A subset S of V is a maximal independent set if and only if S is an independent set and a dominating set.

Proof. Suppose S is both independent and dominating. Let u ∈ V − S. Then there exists an edge e ∈ E such that u ∈ e and e − {u} ⊆ S. Hence e ⊆ S ∪ {u} so that S ∪ {u} is not an independent set. Hence S is a maximal independent set. Conversely, let S be a maximal independent set. Let u ∈ V − S. Since S ∪ {u} is not an independent set, there exists e ∈ E such that e ⊆ S ∪ {u}. Since S is independent, e ̸⊆ S. Hence it follows that u ∈ e and e − {u} ⊆ S. Thus u is dominated by S and hence S is a dominating set of H.

Theorem 2.6. Every maximal independent set S of H is a minimal dominating set of H.

Proof. It follows from Theorem 2.5 that S is a dominating set of H. If S is not a minimal dominating set, then there exists u ∈ S such that S − {u} is a dominating set of H. Hence there exists an edge e ∈ E such that u ∈ e and e − {u} ⊆ S − {u}. Hence e ⊆ S which is a contradiction. Hence S is a minimal dominating set of H.

Definition 2.5. Let H = (V, E) be a hypergraph. Let i(H) = min{|S| : S is a maximal independent set of H} and β0(H) = max{|S| : S is a maximal independent set of H}. Then i(H) is called the independent domination number of H and β0(H) is called the independence number of H.

Theorem 2.7. Let H = (V, E) be any hypergraph. Then γ(H) ≤ i(H) ≤ β0(H) ≤ Γ(H).

Proof. The result follows from Theorem 2.6.

As in graphs we use the minimality condition for domination given in Theorem 2.4 to introduce the concept of irredundance.

Definition 2.6. Let H = (V, E) be a hypergraph. A subset S of V is called an irredundant set if for every vertex u ∈ S one of the following holds.

• (i) If e ∈ E and u ∈ e, then e ∩ (V − S) ̸= ∅.
• (ii) There exists a vertex v ∈ V − S such that if e is any edge in E with v ∈ e and e − {v} ⊆ S, then u ∈ e.

We now proceed to prove that irredundance is a hereditary property.

Theorem 2.8. Let H = (V, E) be a hypergraph and let S be an irredundant set in H. Then any subset S¹ of S is also irredundant.

Proof. Let u ∈ S1. Then u ∈ S. Hence (i) or (ii) holds. Suppose (i) holds. Then if e ∈ E and u ∈ e, then e ∩ (V − S) ̸= ∅. Hence e ∩ (V − S1) ̸= ∅. Hence (i) holds for S1.

Suppose (ii) holds. Let e be any edge in E such that v ∈ e and e−{v} ⊆ S1. Then e−{v} ⊆ S. Hence by (ii) u ∈ e. Thus (ii) holds for S1. Hence S¹ is irredundant.

It follows from Theorem 2.8 that an irredundant set S is a maximal irredundant set if and only if S ∪ {v} is not an irredundant set for any v ∈ V − S.

Observation 2.1. Since the minimality condition for domination is the definition of irredundance, it follows that a dominating set S is a minimal dominating set if and only if S is both a dominating set and an irredundant set.

Definition 2.7. Let H = (V, E) be a hypergraph. Let ir(H) = min{|S| : S is a maximal irredundant set of H} and IR(H) = max{|S| : S is a maximal irredundant set of H}. Then ir(H) and IR(H) are respectively called the irredundance number and upper irredundance number of H.

Theorem 2.9. Every minimal dominating set S of a hypergraph H is a maximal irredundant set of H.

Proof. It follows from Observation 2.1 that S is an irredundant set of H. Suppose S is not maximal irredundant. Then there exists v ∈ V − S such that S¹ = S ∪ {v} is an irredundant set.

Now for v ∈ S1, condition (i) or (ii) holds. Suppose (i) holds. Then if e ∈ E and v ∈ e then e ∩ (V − S1) ̸= ∅. Let w ∈ e ∩ (V − S1). Since v ̸∈ e ∩ (V − S1), it follows that w ̸= v. Hence w ∈ e ∩ (V − S). Hence e − v ̸⊆ S. Thus v is not dominated by S, which is a contradiction.

Suppose (ii) holds. Then there exists w ∈ V −S¹ such that if e is any edge in E with w ∈ e and e− {w} ⊆ S1, then v ∈ e. Clearly w ̸= v. Hence v ∈ e∩(V −S) so that (e− {w})∩(V −S) ̸= ∅. Thus w is not dominated by S, which is a contradiction. Hence S is maximal irredundant.

Corollary 2.2. Let H = (V, E) be any hypergraph. Then

\[ir(H) \le \gamma(H) \le i(H) \le \beta_0(H) \le \Gamma(H) \le IR(H).\]

Proof. Follows from Theorem 2.7 and Theorem 2.9. Thus we have the domination chain for hypergraphs.

3. Conclusion and Scope

Though domination in graphs has been extensively investigated, the study of domination in hypergraphs has not received much atention. In Section 1, we have indicated three different perspectives for extending the concept of domination to hypergraphs. Acharya [6] introduced the concept of domination in hypergraphs and in this case any edge e can dominate |e| − 1 vertices in V − D. The definition that we have introduced in this paper uses (ii) and in this case an edge e can dominate just one vertex in V − D. These two definitions are extreme cases. The concept of domination can also be extended to hypergraphs using (iii) and in this case an edge e can dominate j |e| 2 k vertices in V − D. Results in this direction will be presented in a subsequent paper. Our definition of domination has resulted in extending the concept of domination chain in the context of hypergraph.

The domination chain for graphs which was first established by Cockayne et al. [10] has been the focus of more than 100 research papers ([4], Page 76). We expect that the domination chain for hypergraphs developed in this paper will naturally lead to the investigation of several questions for hypergraphs which arise naturally.

References

• [1] G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press (2005).
• [2] C. Berge, Graphs and Hypergraphs, North Holland, Amsterdam (1973).
• [3] C. Berge, Hypergraphs, North Holland, Amsterdam, (1989).
• [4] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcell Dekker (1998).

• [5] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs Advanced Topics, Marcell Dekker (1998).
• [6] B.D. Acharya, Domination in hypergraphs, AKCE Int. J. Combin., 4 (2007), 117–126.
• [7] B.D. Acharya, Domination in hypergraphs II, New Directions in: Proc. Int. Conf-ICDM 2008, Mysore, India, 1–16.
• [8] M.A. Henning and C. Lowenstein, Hypergraphs with large domination number and with edge sizes at least three, Discrete Appl. Math., 160 (2012), 1757–1765.
• [9] C. Bujtas, M.A. Henning, Zs.Tuza, Transversals and domination in uniform hypergraphs, ´ European J. Combin., 33 (2012), 62–71.
• [10] E.J. Cockayne, S.T. Hedetniemi, and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21 (1978), 461–468
• [11] N.J. Rad and E. Shabani, On the complexity of some hop domination parameters, Electronic Journal of Graph Theory and Applications, 7(1) (2019), 77–89.
• [12] D.A. Mojdeh and M. Alishahi, Outer independent global dominating set of trees and unicyclic graphs, Electronic Journal of Graph Theory and Applications, 7(1) (2019), 121–145.