More about edge domination in hyper graph

D. K. Thakkar; Viral Dave

doi:10.22271/maths.2018.v3.i5a.01

Research article · 2018 · Full text

International Journal of Statistics and Applied Mathematics

More about edge domination in hyper graph

D. K. ThakkarViral Dave

Volume 3(5) · Pages 01–06 · DOI: 10.22271/maths.2018.v3.i5a.01 ↗

Research areasAdvanced Graph Theory Research Nuclear Receptors and Signaling

↓ Read full-text PDF5 citations

Abstract

Author-written

In this paper we further prove more results about edge domination in hypergraphs. In particular we prove necessary & sufficient conditions under which the edge domination number of a hypergraph increases or decreases when a vertex is removed from the hypergraph. We have proved that a subset F of E (G) is an edge dominating set of G iff it is a dominating set in G* (Where G* is dual hypergraph of G) also we have proved that if gE (G-v) > gE (G) & if F is a minimum edge dominating set of G then there is an edge e containing v ' e Î F & Prn [e, F] contains two distinct edges.

Summary

Source-checked

Plain-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
- Edge domination is a concept based on the adjacency of edges, which is applicable to both standard graphs and hypergraphs. View evidence ↗
  Why it matters
  Edge domination is a concept based on the adjacency of edges, which is applicable to both standard graphs and hypergraphs.
  In the paper's own words
  “The concept of edge domination requires the adjacency relation among the edges of a graph. The same relation is also available in hypergraphs and therefore we have considered edge domination in hypergraphs [7].”
  Page 1
  Found in: Introduction
  Read it in the full text Open PDF at page 1 ↗
- Understanding how the edge domination number changes when a vertex is removed from a hypergraph is a key area of study in this research. View evidence ↗
  Why it matters
  Understanding how the edge domination number changes when a vertex is removed from a hypergraph is a key area of study in this research.
  In the paper's own words
  “The change in the edge domination number when a vertex is removed from the hypergraph has been studied here.”
  Page 1
  Found in: Introduction
  Read it in the full text Open PDF at page 1 ↗
The question
- The authors aim to establish the necessary and sufficient conditions that cause the edge domination number of a hypergraph to either increase or decrease upon the removal of a vertex. View evidence ↗
  The question
  The authors aim to establish the necessary and sufficient conditions that cause the edge domination number of a hypergraph to either increase or decrease upon the removal of a vertex.
  In the paper's own words
  “In particular we prove necessary & sufficient conditions under which the edge domination number of a hypergraph increases or decreases when a vertex is removed from the hypergraph.”
  Page 1
  Found in: Definition 2.7 Subhypergraph and Partial Subhypergraph
  Read it in the full text Open PDF at page 1 ↗
What they did
- The study utilizes the concepts of subhypergraphs and partial subhypergraphs created by removing a vertex to analyze changes in domination. View evidence ↗
  What they did
  The study utilizes the concepts of subhypergraphs and partial subhypergraphs created by removing a vertex to analyze changes in domination.
  In the paper's own words
  “For this purpose we have considered the subhypergraph & the partial subhypergraph obtain by removing a vertex from the hypergraph.”
  Page 1
  Found in: Introduction
  Read it in the full text Open PDF at page 1 ↗
- The authors use the dual hypergraph (G*) to relate edge dominating sets in the original hypergraph to dominating sets in the dual. View evidence ↗
  What they did
  The authors use the dual hypergraph (G*) to relate edge dominating sets in the original hypergraph to dominating sets in the dual.
  In the paper's own words
  “We have proved that a subset F of E (G) is an edge dominating set of G iff it is a dominating set in G* (Where G* is dual hypergraph of G)”
  Page 1
  Found in: Introduction
  Read it in the full text Open PDF at page 1 ↗
What they found
- The authors demonstrate via example that removing a vertex can increase the edge domination number, such as when it increases from 1 to 2. View evidence ↗
  What they found
  The authors demonstrate via example that removing a vertex can increase the edge domination number, such as when it increases from 1 to 2.
  In the paper's own words
  “Note that E (G) = 1, also observe that E (G – 9) = 2. Here, E (G – v) > E (G).”
  Page 2
  Found in: Introduction
  Read it in the full text Open PDF at page 2 ↗
- The authors demonstrate via example that removing a vertex can decrease the edge domination number, such as when it decreases from 2 to 1. View evidence ↗
  What they found
  The authors demonstrate via example that removing a vertex can decrease the edge domination number, such as when it decreases from 2 to 1.
  In the paper's own words
  “Here, E (G) = 2, also observe that E (G – 2) = 1. Here, E (G – v) < E (G).”
  Page 3
  Found in: Introduction
  Read it in the full text Open PDF at page 3 ↗
- The edge domination number decreases after vertex removal if and only if a minimum edge dominating set of the original hypergraph consists of a minimum edge dominating set of the reduced hypergraph plus one edge containing the removed vertex. View evidence ↗
  What they found
  The edge domination number decreases after vertex removal if and only if a minimum edge dominating set of the original hypergraph consists of a minimum edge dominating set of the reduced hypergraph plus one edge containing the removed vertex.
  In the paper's own words
  “Theorem 3.2: Let G be a hypergraph & 𝑣  𝑉(𝐺) such that {𝑣} is not an edge of G then E(G – v) < E(G) iff there is a minimum edge dominating set F of G  F = F1  {e} for some minimum edge dominating set F1 of G & some edge e of G containing v.”
  Page 3
  Found in: Definition 2.7 Subhypergraph and Partial Subhypergraph
  Read it in the full text Open PDF at page 3 ↗
- If the edge domination number decreases upon removing a vertex, the decrease is exactly by 1. View evidence ↗
  What they found
  If the edge domination number decreases upon removing a vertex, the decrease is exactly by 1.
  In the paper's own words
  “Corollary 3.3: Let G be a hypergraph & v  V (G) such that {v} is not an edge of G if E (G – v) < E (G) then E (G – v) = E (G) – 1”
  Page 3
  Found in: Definition 2.7 Subhypergraph and Partial Subhypergraph
  Read it in the full text Open PDF at page 3 ↗
- The edge domination number increases after vertex removal if every minimum edge dominating set contains the vertex and no subset of edges of size less than or equal to the original domination number can dominate the reduced hypergraph while leaving an edge incident to the removed vertex. View evidence ↗
  What they found
  The edge domination number increases after vertex removal if every minimum edge dominating set contains the vertex and no subset of edges of size less than or equal to the original domination number can dominate the reduced hypergraph while leaving an edge incident to the removed vertex.
  In the paper's own words
  “Theorem 3.5: Let G be a hypergraph & 𝑣  𝑉(𝐺) such that {v} is not an edge of G then E (G – v) > E (G) iff the following conditions are satisfied 1. V  V (F), for every minimum edge dominating set F of G. 2. There is no subset F of E (G)  |F|  E (G), NE (v)  (E (G) – F)   & F edge dominates G – V.”
  Page 3
  Found in: Definition 2.7 Subhypergraph and Partial Subhypergraph
  Read it in the full text Open PDF at page 3 ↗
- A decrease in the edge domination number occurs if there is a minimum edge dominating set containing an edge 'e' (which contains vertex 'v') such that 'e' is in its own private neighbourhood and its private neighbourhood is a subset of the edges incident to 'v'. View evidence ↗
  What they found
  A decrease in the edge domination number occurs if there is a minimum edge dominating set containing an edge 'e' (which contains vertex 'v') such that 'e' is in its own private neighbourhood and its private neighbourhood is a subset of the edges incident to 'v'.
  In the paper's own words
  “Theorem 3.8: Let G be a hypergraph & v  V (G) such that {v} is not an edge of G then E (G – v) < E (G) iff there is a minimum edge dominating set F & edge e containing v of G  e  F & the following two conditions are satisfied. 1. e  Prn [e, F] 2. Prn [e, F] is a subset of NE (v)”
  Page 4
  Found in: Definition 2.7 Subhypergraph and Partial Subhypergraph
  Read it in the full text Open PDF at page 4 ↗
- For hypergraphs without isolated vertices, a subset of edges is an edge dominating set if and only if it is a dominating set in the dual hypergraph. View evidence ↗
  What they found
  For hypergraphs without isolated vertices, a subset of edges is an edge dominating set if and only if it is a dominating set in the dual hypergraph.
  In the paper's own words
  “Proposition 3.10: Let G be a hypergraph without isolated vertices. A subset F of E (G) is an edge dominating set of G iff it is a dominating set in G*.”
  Page 5
  Found in: Preliminaries Definition 2.1 Hypergraph [4]
  Read it in the full text Open PDF at page 5 ↗
- If the edge domination number increases after removing vertex 'v', then any minimum edge dominating set must contain an edge 'e' incident to 'v' whose private neighbourhood contains at least two distinct edges. View evidence ↗
  What they found
  If the edge domination number increases after removing vertex 'v', then any minimum edge dominating set must contain an edge 'e' incident to 'v' whose private neighbourhood contains at least two distinct edges.
  In the paper's own words
  “Theorem 3.14: Let G be a hypergraph & v  V(G) such that {v} is not an edge of G if E(G – v) > E(G) & if F is a minimum edge dominating set of G then there is an edge e containing v  e  F & Prn[e, F] contains two distinct edges.”
  Page 6
  Found in: Definition 2.7 Subhypergraph and Partial Subhypergraph
  Read it in the full text Open PDF at page 6 ↗
What it means
- The authors conclude that they have successfully analyzed the effects of vertex and edge removal on edge domination in hypergraphs. View evidence ↗
  What it means
  The authors conclude that they have successfully analyzed the effects of vertex and edge removal on edge domination in hypergraphs.
  In the paper's own words
  “In this paper we have studied edge domination in hypergraphs and the operations of vertex removal and edge removal.”
  Page 6
  Found in: Concluding Remarks
  Read it in the full text Open PDF at page 6 ↗
- The authors suggest that future work could introduce and study the concept of 'total edge domination' and how vertex/edge removal affects it. View evidence ↗
  What it means
  The authors suggest that future work could introduce and study the concept of 'total edge domination' and how vertex/edge removal affects it.
  In the paper's own words
  “Further a new concept like total edge domination can be introduced in hypergraphs and the effect of above operations can be studied for total edge domination in hypergraphs.”
  Page 6
  Found in: Concluding Remarks
  Read it in the full text Open PDF at page 6 ↗

Visual summary

1 visuals

Illustrations explain the paper; they do not show study data.

Vertex Removal Effects
AI-generated conceptual illustration (A mathematical hypergraph consisting of small spheres as vertices and translucent colored overlapping loops as hyper-ege). It explains the idea and does not show study data.
View source evidence ↗

Figures & tables

From the original paper

Figure 1Page 2

Figure 2Page 3

FULL TEXT Original article · reflowed for reading

Introduction

Edge dominating set & edge domination number have been explored by several authors [5,6] . The concept of edge domination requires the adjacency relation among the edges of a graph. The same relation is also available in hypergraphs and therefore we have considered edge domination in hypergraphs [7] . The change in the edge domination number when a vertex is removed from the hypergraph has been studied here. For this purpose we have considered the subhypergraph & the partial subhypergraph obtain by removing a vertex from the hypergraph.

Preliminaries Definition 2.1 Hypergraph [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). [4] : Let G be a hypergraph. For every v  V (G) define 𝑣̅ as [1] : Let G be a hypergraph & 𝑆  𝑉(𝐺) then S is said to be a dominating set of G if for every 𝑣  𝑉(𝐺) -𝑆 t here 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  (𝐺). Definition 2.5 Edge Dominating Set [7] : 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.

Definition 2.2 Edge Degree

Definition 2.3 Dual Hypergraph

Definition 2.4 Dominating Set in Hypergraph

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.6 Minimal Edge Dominating Set [7] : 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. [3] : Let G be a hypergraph & 𝑣  𝑉(𝐺). Consider the subset 𝑉(𝐺) -{𝑣} 𝑜𝑓 𝑉(𝐺). this set will induce two types of hypergraphs from G.

Definition 2.7 Subhypergraph and Partial Subhypergraph

Since F 1 is an edge dominating set of Gv, there is some g  F 1  h is adjacent to g, then g  F also. Thus h is adjacent to some member of F also. Suppose v  h then h  e   because v  h. Therefore, h is adjacent to e & e  F. Thus, F is an edge dominating set of G. Obviously F is a minimum edge dominating set of G.

Conversely, suppose the condition is satisfied.

Let F be a minimum edge dominating set of G such that F = F 1  {e} for some minimum edge dominating set F 1 of Gv & for some edge e containing v. Then

From the proof of the above theorem it is clear that every minimum edge dominating set F 1 of Gv & every edge e containing v give rise to a minimum edge dominating set of G namely F 1 = F  {v}. Suppose there are k distinct minimum edge dominating set of Gv & suppose the edge degree of v = j, then in the above manner they will generate kj minimum edge dominating set of G. It follows that the number of minimum edge dominating set of G  the number of minimum edge dominating set of Gv. Now, we stat & prove a set of necessary and sufficient conditions under which the edge domination number of a hypergraph increases when a vertex v is removed from the hypergraph.

1. Suppose there is a minimum edge dominating set F of G  v  V(F) then F is a set of edges of Gv. Let h be any edge of G v then h is also an edge of G & therefore h  g   for some g  F. Thus F is an edge dominating set of Gv.

2. Suppose the set F mentioned in statement (2) of the theorem exists.

Which is again a contradiction. Thus condition (2) also holds.

Let F be a minimum edge dominating set of Gv, then v  V (F). Suppose F is an edge dominating set of G also. Then F is a minimum edge dominating set of G. Thus, F is a minimum edge dominating set of G  v  V (F). This is a contradiction to (1). Therefore, let's assume that F is not an edge dominating set of G. Therefore there is an edge h  v  h & h is not adjacent with any First suppose that  E (Gv) =  E (G). Let F be a minimum edge dominating set of Gv. First suppose that F is an edge dominating set of G. Then F is a minimum edge dominating set of G not containing any edge containing v. This is a contradiction to (1). Suppose F is not an edge dominating set of G -v. Therefore, no edge containing v can be a member of F. Thus, F  N E (v) =, |F|   E (G) & F is an edge dominating set of Gv. This is a contradiction to (2). Therefore,

Let F be a minimum edge dominating set of Gv then F cannot be an edge dominating set of G. Therefore, no edge containing v can be a member of F. Thus, F   For some j in 1, 2… k Prn [e j , F] contains atleast two distinct edges.

Concluding Remarks

In this paper we have studied edge domination in hypergraphs and the operations of vertex removal and edge removal. Further a new concept like total edge domination can be introduced in hypergraphs and the effect of above operations can be studied for total edge domination in hypergraphs.

Figures and tables from the paper

References

7 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.
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.

Cited by 4

From OpenAlex, OpenCitations and reference lists read by Scinovex

Edge Stable Sets and Secured Edge Stable Sets in Hypergraphs ↗
D. K. Thakkar, V. R. Dave · International Journal of Mathematical Sciences and Computing · 2019
In this paper, we have proved several results regarding edge stable sets and maximal edge stable sets in hypergraphs.We have also proved various results regarding edge stable sets and maximal edge stable sets in partial subhypergraphs.We have introduced the concept of secured edge stable set, maximum secured edge stable set and 𝑖 𝑠 1 -Set in this paper and proved…
❝ 3PDF
A sharp upper bound for the edge dominating number of hypergraphs with minimum degree ↗
Zhongzheng Tang, Zhuo Diao · Journal of Combinatorial Optimization · 2025
❝ 0
Edge Stable Sets and Edge Independent Sets in Hypergraphs ↗
D. K. Thakkar, V.R. Dave · Journal of Mathematics and Informatics · 2018
In this paper we have introduce two new concepts namely edge stable sets& edge independent sets in hypergraphs.We have proved a necessary and sufficient condition under which an edge stable set is a maximal edge stable set.We have also proved an important result that an edge stable set of a hypergraph is a maximal edge stable set of it if…
❝ 0PDF
About Edge Independent Sets in Hypergraphs ↗
D. K. Thakkar, V. R. Dave · International Journal of Scientific Research in Mathematical and Statistical Sciences · 2018
The International Scientific Research Organization for Science, Engineering and Technology (ISROSET) is a Non-Profit Organization; The ISROSET is dedicated to improvement in academic sectors of Science (Chemistry, Bio-chemistry, Zoology, Botany, Biotechnology, Pharmaceutical Science, Bioscience, Bioinformatics, Biometrics, Biostatistics, Microbiology, Environmental Management, Medical Science, Forensic Science, Home Science, Library Science, Material Science Military Science, Physical Science, Physical Education Science, Educational Science, Fisheries,…
❝ 0PDF

[1] Acharya B, Domination in Hypergraphs, AKCE J. Graphs. Combin. 2007; 4(2):111-126.

[2] Behr A, Camarinopoulos L. On the domination of hypergraphs by their edges, Discrete Mathematics. 1998; 187:31-38.

[3] Berge Graphs C. Hypergraphs, North-Holland, Amsterdam, 1973.

[4] Berge C. Hypergraphs, North-Holland Mathematical Library, New York, 1989, 45.

[5] Haynes T, Hedetniemi S, Slater P. Domination in Graphs Advanced Topics, Marcel Dekker, Inc. New York, 1998.

[6] Haynes T, Hedetniemi S, Slater P. Fundamental of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.

[7] Thakkar D, Dave V. Edge Domination in Hypergraph, International Journal of Mathematics & Statistics Invention. 2017; 5(9):13-17.

Abstract

Summary

1Why it matters

2The question

3What they did

4What they found

5What it means

Visual summary

Vertex Removal Effects

Figures & tables

Introduction

Preliminaries Definition 2.1 Hypergraph [4]

Definition 2.2 Edge Degree

Definition 2.2 Edge Degree

Definition 2.3 Dual Hypergraph

Definition 2.3 Dual Hypergraph

Definition 2.4 Dominating Set in Hypergraph

Definition 2.7 Subhypergraph and Partial Subhypergraph

Concluding Remarks

Figures and tables from the paper

References

Cited by 4

Why it matters

The question

What they did

What they found

What it means