Research article · 2018 · Full text
International Journal of Statistics and Applied MathematicsEdge restrainedness in hypergraph
Volume 3(6) · Pages 124–130
Research areasgraph theory and CDMA systemsAdvanced Graph Theory Research
Abstract
Author-writtenIn this paper we have introduced edge restrained set and one maximal edge restrained set in hypergraph. We have also introduced RE – Set and RE – Number in hypergraph. We have given characterization of one maximal edge restrained sets. We have also proved that in a hypergraph with minimum edge degree at least two every one – maximal edge restrained set is an edge h – dominating set. We have proved several results about edge restrainedness in subhypergraphs and partial subhypergraphs also.
Summary
Source-checkedPlain-language reading of the full paper, prepared with AI and checked against the text. Each point links to the authors' own words.
Why it matters
- The study builds upon previous research into restrained domination and vertex restrainedness to explore the concept of edge restrainedness specifically within hypergraphs. View evidence ↗
The question
- The authors aim to define and characterize edge restrained sets, one maximal edge restrained sets, and the associated RE-sets and RE-numbers in hypergraphs. View evidence ↗
What they did
- The research assumes a hypergraph model where any two distinct edges intersect in at most one vertex. View evidence ↗
- An edge restrained set is defined as a set of edges F where every edge not in F is adjacent to at least one other edge also not in F. View evidence ↗
- A one maximal edge restrained set is an edge restrained set F such that adding any single edge from the remaining set makes it no longer edge restrained. View evidence ↗
What they found
- The authors demonstrate that edge restrainedness is neither a hereditary nor a super hereditary property. View evidence ↗
- For any one maximal edge restrained set F, the number of edges in the complement set E(G) – F is always even. View evidence ↗
- The RE-number of a hypergraph is odd if and only if the total number of edges in the hypergraph is odd. View evidence ↗
- In hypergraphs with a minimum edge degree of at least 2, every one-maximal edge restrained set also functions as an edge h-dominating set. View evidence ↗
- The RE-number of a hypergraph is at least the maximum edge degree minus 2 (RE(G) ≥ ΔE(G) – 2). View evidence ↗
- The authors provide an example showing that the RE-number of a sub-hypergraph can be greater than that of the original hypergraph. View evidence ↗
- A set of edges F in a partial sub-hypergraph G-v is edge restrained if and only if the union of F and the neighborhood of v is edge restrained in the original hypergraph G. View evidence ↗
What it means
- The authors suggest that future research should investigate how removing an edge affects the RE-number and explore edge restrained dominating sets. View evidence ↗
Visual summary
1 visualsIllustrations explain the paper; they do not show study data.
Concept of Edge Restrainedness
AI-generated conceptual illustration (A mathematical hypergraph consisting of colored dots and overlapping translucent loops). It explains the idea and does not show study data.
View source evidence ↗Figures & tables
From the original paper
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5Introduction
The concept of restrained domination was studied by [5] . From this concept a new concept of restrainedness of vertices was introduced by D. K. Thakkar and B. M. Kakrecha [12] . Now we consider the concept of restrainedness of edges of hypergraphs. Here we defined edge restrained sets and one maximal edge restrained sets in hypergraphs. We characterize one maximal edge restrained sets. We also define RE -Sets and RE -Number of a hypergraph. We proved that REnumber of a hypergraph is odd if and only if the number of edges of the hypergraph is odd. We prove several results related to the edge restrainedness in subhypergraphs and partial subhypergraphs. [4] : A hypergraph 𝐺 is an ordered pair (𝑉(𝐺), 𝐸(𝐺)) where 𝑉(𝐺) is a non-empty finite set & 𝐸(𝐺) is a family of non-empty subsets of 𝑉(𝐺) their union = 𝑉(𝐺). The elements of 𝑉(𝐺) are called vertices & the members of 𝐸(𝐺) are called edges of the hypergraph 𝐺. We make the following assumption about the hypergraph. 1. Any two distinct edges intersect in at most one vertex. [4] : Let G be a hypergraph & v V(G) then the edge degree of v = d E (v) = the number of edges containing the vertex v. The minimum edge degree among all the vertices of G is denoted as E (G) and the maximum edge degree is denoted as E (G). [1] : Let G be a hypergraph & 𝑆 𝑉(𝐺) then S is said to be a dominating set of G if for every 𝑣 𝑉(𝐺) -𝑆 there is 𝑢 𝑆 u and v are adjacent vertices. A dominating set with minimum cardinality is called minimum dominating set and cardinality of such a set is called domination number of G and it is denoted as (𝐺). [8] : Let G be a hypergraph & 𝑆 𝐸(𝐺) then S is said to be an edge dominating set of G if for every 𝑒 𝐸(𝐺) -𝑆 there is some f in S e and f are adjacent edges. An edge dominating set with minimum cardinality is called a minimum edge dominating set and cardinality of such a set is called edge domination number of G and it is denoted as E (G). Definition 2.5 Minimal Edge Dominating Set [8] : Let G be a hypergraph & 𝐹 𝐸(𝐺) then F is said to be a minimal edge dominating set if (1) F is an edge dominating set (2) No proper subset of F is an edge dominating set of G. Definition 2.6 Sub hypergraph and Partial sub hypergraph [3] : Let G be a hypergraph & 𝑣 𝑉(𝐺). Consider the subset 𝑉(𝐺) -{𝑣} 𝑜𝑓 𝑉(𝐺). This set will induce two types of hypergraphs from G.
Preliminaries Definition 2.1 Hypergraph
Preliminaries Definition 2.1 Hypergraph
Definition 2.2 Edge Degree
Definition 2.2 Edge Degree
Definition 2.3 Dominating Set in Hypergraph
Definition 2.3 Dominating Set in Hypergraph
Definition 2.4 Edge Dominating Set
(1) First type of hypergraph: Here the vertex set = 𝑉(𝐺)-{𝑣} and the edge set = { 𝑒 / 𝑒 = 𝑒 -{𝑣} 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑒 𝐸(𝐺) }. This hypergraph is called the sub hypergraph of G & it is denoted as 𝐺 -{𝑣}.
(2) Second type of hypergraph: Here also the vertex set = 𝑉(𝐺) -{𝑣} and edges in this hypergraph are those edges of G which do not contain the vertex v.This hypergraph is called the partial sub hypergraph of G. Definition 2.7 Edge Neighbourhood [3] : Let G be a hypergraph & e be any edge of G then Open edge neighbourhood of e = 𝑁(𝑒) = { 𝑓 𝐸(𝐺) /𝑓 𝑖𝑠 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡 𝑡𝑜 𝑒 }.
Close edge neighbourhood of e = 𝑁[𝑒] = 𝑁(𝑒) {𝑒}. [3] : Let G be a hypergraph. F be a set of edges & e F, then the private neighbourhood of e with respect to set
Definition 2.8 Private Neighbourhood of an edge
Here we are introducing a new concept called edge hdomination in hypergraph. [11] : Obviously F is an edge restrained set in hypergraph. Let F 1 = {e 1 , e 2 }. Note that F 1 is not an edge restrained set. Thus, restrainedness is not a super hereditary property. Let F 1 = {e 1 , e 3 }. Note that F 1 is not an edge restrained set. Thus, restrainedness is not a hereditary property.
Definition 2.9 Edge h -Dominating Set
Definition 2.9 Edge h -Dominating Set
Definition 3.5 (One Maximal Edge Restrained Set):
Let G be a hypergraph and F be an edge restrained set of G then F is said to be a one maximal edge restrained set if F {e} is not an edge restrained set for every e E(G) -F. Therefore, e & f are adjacent edges. Thus, we have proved that F is an edge restrained set of G. (b) Let F be a set of edges E(G) -F has exactly two distinct edges. It is obvious that F is a one maximal edge restrained set of G. Thus, we have proved that F is a set of edges E(G) -F has exactly two distinct edges than F is a one maximal edge restrained set. Conversely suppose F is a one maximal edge restrained set of G. Suppose E(G) -F has at least three edges. Let e E(G) -F. Than E(G) -(F {e}) has at least two edges and therefore by (a) F {e} is an edge restrained set of G. This contradicts the one maximality of F. E(G) -F must have exactly two distinct edges. Thus, we conclude that a set F of edges is a one maximal edge restrained set of G if and only if E(G) -F has exactly two distinct edges. We also conclude that all one maximal edge restrained sets have the same cardinality r 2r -1.
Definition 3.8 (RE -Set):
Let G be a hypergraph. A one maximal edge restrained set with minimum cardinality is called a RE -Set of G. The cardinality of a RE -Set is called the REnumber of G and it is denoted by RE(G). Example 3.9: Consider the finite projective plane mentioned above. It is obvious that every one maximal edge restrained set is a RE -Set of G. Therefore, REnumber of this hypergraph is r 2r -1.
Characterization of one maximal edge restrained set:
Now, we give a characterization of one maximal edge restrained sets Theorem 3.10: Let G be a hypergraph and F be an edge restrained set of G. Then F is a one maximal edge restrained set if and only if for every e E(G) -F there is an edge f in E(G) -F which is adjacent to only one edge of E(G) -F namely e.
Proof: Suppose F is a one maximal edge restrained set of G. Let e E(G) -F. Since F {e} is not an edge restrained set of G there is an edge f in E(G) -(F {e}) such that f is not adjacent to any edge of E(G) -(F {e}). Now, f E(G) -F and therefore f must be adjacent to some edge of E(G) -F. This edge must be e. Thus, f is adjacent to e. Suppose f is adjacent to some edge h h e and f is adjacent to h. This will imply that f is adjacent to h and h is an edge of E(G) -(F {e}). This contradicts the earlier statement that f is not adjacent to any edge of E(G) -(F {e}). Therefore, f is adjacent to only one edge of E(G) -F namely e. Conversely suppose the condition is satisfied. Let e E(G) -F. Let f be an edge of E(G) -F such that f is adjacent to only one edge of E(G) -F namely e. This implies that f is an edge of E(G) -(F {e}) which is not adjacent to any edge of E(G) -(F {e}). This proves that F {e} is not an edge restrained set of G. Thus, F is a one maximal edge restrained set of G. The above theorem can be improved further. Theorem 3.11: Let G be a hypergraph and F be an edge restrained set of G. Then F is a one maximal edge restrained set of G if and only if for every e E(G) -F there is a unique f in E(G) -F f is adjacent to only one edge in E(G) -F namely e.
Proof: First suppose that F is a one maximal edge restrained set of G. Let e E(G) -F. By the above theorem there is an edge f in E(G) -F f is adjacent to only one edge in E(G) -F namely e. Now, f E(G) -F therefore by the above theorem there is an edge h in E(G) -F h is adjacent to only one edge in E(G) -F namely f. Thus, f is adjacent to e as well as h and h, e E(G) -F. Therefore, h = e. Thus, e is adjacent to only one edge in E(G) -F namely f. Thus, f is unique for e. Conversely suppose the condition is satisfied. Let e E(G) -F and let f be the unique edge in E(G) -F which is adjacent to only one edge in E(G) -F namely e. By the above theorem the set F is the one maximal edge restrained set. Corollary 3.12: Let G be a hypergraph and F be a one maximal edge restrained set of G then E(G) -F has even number of edges.
Proof:
For every e E(G) -F there is a unique edge f e in E(G) -F f e is adjacent to only one edge in E(G) -F namely e. Define the function H: E(G) -F E(G) -F as H(e) = f e Then H is oneone and onto function from E(G) -F E(G) -F |E(G) -F| is an even number. Thus, E(G) -F has even number of edges. Proof: First we recall that a set F is an edge hdominating set if it satisfies the following condition.
(1) All isolated edges of G are in F.
(2) If f is not an isolated edge & f F then there is a vertex x in f edge degree of x 2 & all the edges containing x except f are in F. Let e E(G) -F. Let f be an edge of E(G) -F f is adjacent to only one edge in E(G) -F namely e. Let f e = {x}. Now, f is the unique edge in E(G) -F e is adjacent to f. Let y be any vertex of e y x. Let h be any edge containing y except e. Then h f and therefore h cannot be an edge of E(G) -F. h F. Thus, every edge which contains y and different from e is in F. This proves that F is an edge hdominating set of G.
Figures and tables from the paper
References
12 in the original paper- Acharya B. Domination in Hypergraphs, AKCE J Graphs. Combin. 2007; 4(2):111-126.
- Behr A, Camarinopoulos L. On the domination of hypergraphs by their edges, Discrete Mathematics. 1998; 187:31-38.
- Berge Graphs C, Hypergraphs. North-Holland, Amsterdam, 1973.
- Berge C. Hypergraphs, North -Holland Mathematical Library, New York, 1989, 45.
- Domke G, Hetting J, Hedetniemi S, Laskar R, Markus L. Restrained Domination in Graphs, Discrete Mathematics, 1999; 203:61-69.
- Haynes T, Hedetniemi S, Slater P. Domination in Graphs Advanced Topics, Marcel Dekker, Inc., New York, 1998.
- Haynes T, Hedetniemi S, Slater P. Fundamental of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
- Thakkar D, Dave V. Edge Domination in Hypergraph, International Journal of Mathematics & Statistics Invention. 2017; 5(9):13-17.
- Thakkar D, Dave V. More about Edge Domination in Hypergraph, International Journal of Statistics and Applied Mathematics. 2018; 3(5):01-06.
- Thakkar D, Dave V. Regarding Edge Domination in Hypergraph, International Journal of Mathematics Trends & Technology. 2017; 44(3):108-114.
- Thakkar D, Dave V. Edge h -Domination in Hypergraph, IJMA. 2017; 8:8.
- Thakkar D, Kakrecha B. Maximal Restrained Sets in Graph, International Journal of Mathematics and Soft Computing. 2014; 4(2):207-211.