Electronic Journal of Graph Theory and Applications 12 .
, 181Ae188 A new look at the concept of domination in Divyaa .
Ramakrishnanb .
Arumugamc Department of Mathematics.
College.
Kanuur b Department of Mathematics.
Kannur University.
Kannur.
Kerala c Adjunct Professor.
Department of Computer Science and Engineering Ramco Institute of Technology.
Rajapalayam-626 117.
Tamil Nadu.
India.
divyapmadhavan@gmail.
com, ramakrishnantvknr@gmail.
com, s.
arumugam@ritrjpm.
Abstract 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 Oe S, there exists an edge e OO E such that v OO e and e Oe .
OI 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.
Introduction By a graph G = (V.
E) we mean a finite undirected graph with neither loops nor multiple For graph theoretic terminology we refer to Chartrand and Lesniak .
For terminology in hypergraphs we refer to Berge .
, .
Received: 22 November 2020.
Revised: 18 January 2022.
Accepted: 13 May 2024.
A new look at the concept of domination in hypergraphs Divya et al.
A hypergraph H is an ordered pair (V.
E) where V is aSfinite nonempty set and E is a subset of the power set P(V ) such that .
Ou 2 for all e OO E and e = V.
A hypergraph H is called a eOOE simple hypergraph if no edge is a proper subset of another edge.
Two vertices u, v OO V are called adjacent if there exists an edge e OO E such that .
, .
OI e.
Throughout this paper we consider only simple hypergraphs.
A hypergraph H is called a k-uniform hypergraph if .
= k for all e OO E.
E = .
: e OI V and .
= .
, then H is called a complete k-uniform hypergraph.
Let H = (V.
E) be a hypergraph.
A hypergraph H1 = (V1 .
E1 ) is called a subhypergraph of H if V1 OI V and E1 OI E.
Domination in graphs has been extensively investigated.
An excellent treatment of fundamentals of domination is given in .
For survey of several advanced topics in domination we refer to .
For recent results on domination related parameters we refer to .
, .
Let G = (V.
E) be a graph.
A subset D OI V is called a dominating set of G if for every vertex v in V Oe D, there exists u OO 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.
If G is a path Pn or a cycle Cn of order n, then (G) = n3 .
Definition 1.
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 OE S is a P -set.
A P -set S is a 1-maximal P -set if S O .
is a P -set for every v OO V Oe S.
Theorem 1.
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.
For further details we refer to (.
Page 67-.
The concept of domination in graphs can be looked at from three different perspectives.
Let D OI V (G) and let v OO V Oe D.
Then D is a dominating set of G if and only if one of the following .
There exists a vertex u OO D such that uv is an edge of G.
There exists an edge e OO E such that v OO e and e Oe .
OI lD.
There exists an edge e OO E such that v OO e and |D O .
Ou .
Acharya .
introduced the concept of domination in hypergraphs using .
Definition 1.
Let H = (V.
E) be a hypergraph.
A subset D of V is called a dominating set of H if for every v OO V Oe D, there exists u OO D such that u and v are adjacent.
Further results on domination in hypergraphs are given in .
, 7, .
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 .
In fact if G is the graph with V (G) = V (H) and the subgraph of G induced by the set A new look at the concept of domination in hypergraphs Divya et al.
of all vertices of any edge e is K.
, 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 .
, so that this coincides with the usual concept of domination when restricted to graphs.
Main Results We start with a new look at the concept of domination in hypergraphs.
Definition 2.
Let H = (V.
E) be a hypergraph.
A subset D of V is called a dominating set of H if for every v OO V Oe D, there exists an edge e OO E such that v OO e and e Oe .
OI D.
The minimum cardinality of a dominating set of H is called the domination number of H and is denoted by (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 .
Oe 1 vertices in V Oe D whereas according to Definition 2.
1, e dominates just one vertex in V Oe D.
Hence the domination number obtained by using Definition 2.
1 may be much larger than the domination number obtained from Definition 1.
Example 2.
For the complete r-uniform hypergraph Knr , we have (Knr ) = r Oe 1.
The complete r-partite r-uniform hypergraph H = (V.
E) is such that V can be partitioned into r nonempty subsets V1 .
V2 , .
Vr and E = .
OI V : .
= r and .
O Vi | = 1 for each If |Vi | = ni , we denote this hypergraph by H = Knr 1 ,n2 ,.
,nr .
Clearly If D OI V, |D| = r Oe 1 and |D O Vi | = 1 for all i, 1 O i O r Oe 1, then D is a minimum dominating set of H.
Hence (H) = r Oe 1.
In particular consider |H = K2,2,3 where the partite sets are V1 = .
1 , a2 }.
V2 = .
1 , b2 } and V3 = .
1 , c2 , c3 }.
Let D = .
1 , b1 }.
Since e = .
1 , b1 , c1 } is an edge in H, it follows that c1 is dominated by D.
Similarly D dominates all the vertices of H.
Definition 2.
A vertex v of a hypergraph H is called a pendent vertex if v OO e for exactly one edge e of H.
The r-uniform linear path Pmr is the hypergraph H = (V.
E) where V = .
i : 1 O i O m.
Oe .
E = .
1 , e2 , .
, em } and .
1 , v2 , .
, vr }, if i = 1, .
Oe.
rOe.
Oe.
, .
, virOe.
Oe.
}, if 2 O i O m.
Theorem 2.
Let H = Pmr be the r-uniform linear path.
Then m 1 if r = 2, (H) = m.
Oe .
1, if r Ou 3.
A new look at the concept of domination in hypergraphs Divya et al.
Proof.
If r = 2, then H is the path Pm 1 and hence by Theorem 1.
1, (H) = (Pm 1 ) = m 1 Suppose r Ou 3.
The vertices v1 , v2 , v3 , .
, vrOe1 lie only on edge e1 and hence are pendent vertices.
The vertices vr 1 , vr 2 , .
, vrOe2 lie only on the edge e2 and hence are pendent vertices.
In general, all the vertices of ei Oe .
Oe.
rOe.
Oe.
, virOe.
Oe.
} are pendent vertices and hence each edge of H has at least r Oe 2 pendent vertices.
Now, choose a pendent vertex wi in ei where 1 O i O m.
Then D = V Oe .
i : 1 O i O .
is a dominating set of H and |D| = |V | Oe m = m.
Oe .
Hence (H) O m.
Oe .
Now let S be any dominating set of H.
Since each edge of H has at least r Oe 2 pendent vertices, it follows that at most one pendent vertex of any edge is not in S.
Hence |S| Ou |V | Oe m = m.
Oe .
Thus (H) = m.
Oe .
The r-uniform linear cycle Cm is the hypergraph H = (V.
E) where V = .
i : 1 O i O m.
Oe .
E = .
1 , e2 , .
, em } and if i = 1, .
1 , v2 , .
, vr }, .
Oe.
rOe.
Oe.
, .
, virOe.
Oe.
, if 2 O i O m Oe 1, .
Oe.
rOe.
Oe.
, .
, vm.
Oe.
, v1 }, if i = m.
Theorem 2.
Let H = Cm be the r-uniform cycle.
Then m if r = 2, (H) = m.
Oe .
, if r Ou 3.
Proof.
If r = 2, then H is the cycle Cm and hence by Theorem 1.
2, (H) = (Cm ) = m3 .
Suppose r Ou 3.
As in Theorem 2.
3, we observe that every edge of H contains rOe2 pendent vertices.
Now, choose a pendent vertex wi in ei where 1 O i O m.
Then D = V Oe .
i : 1 O i O .
is a dominating set of H and |D| = |V | Oe m = m.
Oe .
Hence (H) O m.
Oe .
Now, let S be any dominating of H.
Since each edge of H has exactly r Oe 2 pendent vertices, it follows at most pendent vertex of any edge is not in S.
Hence |S| Ou |V | Oe m = m.
Oe .
Thus (H) Ou m.
Oe .
and so (H) = m.
Oe .
Let H = (V.
E) be a hypergraph and let k = min .
Since .
Ou 2 for all e OO E, we have eOOE k Ou 2.
In the following theorem we prove that k Oe 1 is a lower bound for (H).
We also determine all hypergraphs for which (H) = k Oe 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.
E O ) where E O = {S O .
: v OO V Oe S}.
Theorem 2.
Let H = (V.
E) be a hypergraph and let k = min .
and k Ou 2.
Then (H) Ou k Oe1 eOOE and equality holds if and only if there exists a proper subset S of V such that |S| = k Oe 1 and H(S) is a subhypergraph of H.
Proof.
Let S be any dominating set of H and let v OO V OeS.
Then there exists e OO E such that v OO e and e Oe .
OI S.
Hence |S| Ou .
Oe 1 Ou k Oe 1.
Hence (H) Ou k Oe 1.
Now suppose (H) = k Oe 1.
Let S be a -set of H.
Then for any v OO V Oe S, there exists an edge ev OO E such that ev Oe .
OI S.
Hence ev OI S O .
and |S O .
| = k.
Hence ev = S O .
Let E O = .
v : v OO V Oe S}.
Clearly E(H(S)) = E O OI 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 (H) O |S| = k Oe 1.
A new look at the concept of domination in hypergraphs Divya et al.
Corollary 2.
Let H = (V.
E) be a hypergraph and let |V | = n.
Then (H) = 1 if and only if the star K1,nOe1 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 Oe .
is not a dominating set of H for all v OO S.
In the following theorem we obtain a characterization of minimal dominating sets.
Theorem 2.
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 OO S, one of the following holds.
If e OO E and u OO e, then e O (V Oe S) = OI.
There exists a vertex v OO V Oe S such that if e is any edge in E with v OO e and e Oe .
OI S, then u OO e.
Proof.
Let S be a minimal dominating set of H and let u OO S.
Then S1 = S Oe .
is not a dominating set of H.
Hence there exists a vertex v OO V Oe S1 such that v is not dominated by S1 .
If v = u then .
Suppose u = v.
Let e be any edge of H such that v OO e and e Oe .
OI S.
If u OO e, then v is dominated by S Oe .
, which is a contradiction.
Hence .
Conversely, suppose that for each u OO S, either .
If .
holds, then u is not dominated by S Oe .
If .
holds, then v is not dominated by S Oe .
Hence S Oe .
is not a dominating set H and so S is a minimal dominating set of H.
Definition 2.
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 e(H).
It follows from the definition that (H) O e(H).
We now proceed to introduce the concept of independence in hypergraphs.
Definition 2.
Let H = (V.
E) be a hypergraph.
A subset S of V is called an independent set if e OI S for any e OO E.
Example 2.
Let e OO E be any edge of H.
Since H is a simple hypergraph, .
Ou 2.
Clearly S = e Oe v where v OO 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 O .
is not an independent set for any u OO V Oe S.
Theorem 2.
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 OO V Oe S.
Then there exists an edge e OO E such that u OO e and e Oe .
OI S.
Hence e OI S O .
so that S O .
is not an independent Hence S is a maximal independent set.
Conversely, let S be a maximal independent set.
Let u OO V Oe S.
Since S O .
is not an independent set, there exists e OO E such that e OI S O .
Since S is independent, e OI S.
Hence it follows that u OO e and e Oe .
OI S.
Thus u is dominated by S and hence S is a dominating set of H.
A new look at the concept of domination in hypergraphs Divya et al.
Theorem 2.
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 OO S such that S Oe .
is a dominating set of H.
Hence there exists an edge e OO E such that u OO e and e Oe .
OI S Oe .
Hence e OI S which is a contradiction.
Hence S is a minimal dominating set of H.
Definition 2.
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.
Let H = (V.
E) be any hypergraph.
Then (H) O i(H) O 0 (H) O e(H).
Proof.
The result follows from Theorem 2.
As in graphs we use the minimality condition for domination given in Theorem 2.
4 to introduce the concept of irredundance.
Definition 2.
Let H = (V.
E) be a hypergraph.
A subset S of V is called an irredundant set if for every vertex u OO S one of the following holds.
If e OO E and u OO e, then e O (V Oe S) = OI.
There exists a vertex v OO V Oe S such that if e is any edge in E with v OO e and e Oe .
OI S, then u OO e.
We now proceed to prove that irredundance is a hereditary property.
Theorem 2.
Let H = (V.
E) be a hypergraph and let S be an irredundant set in H.
Then any subset S1 of S is also irredundant.
Proof.
Let u OO S1 .
Then u OO S.
Hence .
Suppose .
Then if e OO E and u OO e, then e O (V Oe S) = OI.
Hence e O (V Oe S1 ) = OI.
Hence .
holds for S1 .
Suppose .
Let e be any edge in E such that v OO e and eOe.
OI S1 .
Then eOe.
OI S.
Hence by .
u OO e.
Thus .
holds for S1 .
Hence S1 is irredundant.
It follows from Theorem 2.
8 that an irredundant set S is a maximal irredundant set if and only if S O .
is not an irredundant set for any v OO V Oe S.
Observation 2.
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.
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.
Every minimal dominating set S of a hypergraph H is a maximal irredundant set of H.
A new look at the concept of domination in hypergraphs Divya et al.
Proof.
It follows from Observation 2.
1 that S is an irredundant set of H.
Suppose S is not maximal Then there exists v OO V Oe S such that S1 = S O .
is an irredundant set.
Now for v OO S1 , condition .
Suppose .
Then if e OO E and v OO e then e O (V Oe S1 ) = OI.
Let w OO e O (V Oe S1 ).
Since v OO e O (V Oe S1 ), it follows that w = v.
Hence w OO e O (V Oe S).
Hence e Oe v OI S.
Thus v is not dominated by S, which is a contradiction.
Suppose .
Then there exists w OO V Oe S1 such that if e is any edge in E with w OO e and e Oe .
OI S1 , then v OO e.
Clearly w = v.
Hence v OO e O (V Oe S) so that .
Oe .
) O (V Oe S) = OI.
Thus w is not dominated by S, which is a contradiction.
Hence S is maximal irredundant.
Corollary 2.
Let H = (V.
E) be any hypergraph.
Then ir(H) O (H) O i(H) O 0 (H) O e(H) O IR(H).
Proof.
Follows from Theorem 2.
7 and Theorem 2.
Thus we have the domination chain for 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 .
introduced the concept of domination in hypergraphs and in this case any edge e can dominate .
Oe 1 vertices in V Oe D.
The definition that we have introduced in this paper uses .
and in this case an edge e can dominate just one vertex in V Oe D.
These two definitions are extreme cases.
The concept of can also be extended to hypergraphs using .
and in this case an edge e can dominate .
vertices in V Oe 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.
has been the focus of more than 100 research papers (.
Page .
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