On knot separability of hypergraphs and its application towards infectious disease management

1.   Introduction

Networks are "everywhere", varying from small to giant and simple to complex. There are some networks that are giant and complex too. For example, virtual social networking, the World Wide Web, the interactions between proteins in the cells of our bodies, etc. are complex and big too. Networks and the epidemiology of directly transmitted infectious diseases like COVID-19 are fundamentally linked ^[1]. It is to be noted that a network irrespective of its size and complexity can be represented by a graph. A graph is a set of objects in which some pair of objects are in some sense "related". The objects are called nodes and the interacted pairs of objects are called edges. Interactions in a graph are always represented in terms of pairs of objects. But, in reality, there are networks where interactions among the objects/nodes may not be pairwise. In that case, the representation of such networks as graphs may not be appropriate. The situation can be well understood in the case of networks like COVID-19 and their spreading, where we may consider the nodes as the people and the linkages as the spreading of the disease. In this case, it may not be always possible to link the nodes pairwise as the rate of infection is too high. In fact, the interaction among the objects occurs in some groups of objects. These interacting groups may contain any number of objects. So, the representation of such networks by a hypergraph becomes more appropriate as compared to graphs, where interaction levels happen among the objects in groups. Many problems in hypergraph theory can be simplified by treating the problem separately into their components and it is of interest to consider the notion of separability and connectedness of the various components. At the same time, it is geometrically evident that the intensity of connectivity can vary widely over different parts of a hypergraph with great complexity. Thus, to determine the characteristics of the components and their connectivity, it is expedient to have a measure of the connectedness of the components within the hypergraph.

In the year 1979, Capobianco and Molluzzo ^[2] defined the strength of a point in a graph as the increase in the number of connected components in the graph upon the removal of the point. This motivates us to study the strength and connectivity of hypergraph theory. Before going to define the strength, we would like to mention here a fundamental concept in hypergraph known as a knot. The concept of knot and knot hyperpath in a hypergraph was first introduced by Rahman et al. in the year 2022 ^[3] and discussed some interesting results related to hyperpaths and hypertrees. A knot in a hypergraph is defined as a non-empty subset of some intersecting hyperedges, which can be treated as the junction of hyperedges as if it were a vertex in a graph whose removal deletes some edges. We note that the cut vertex in the graph can never be an isolated or a pendant vertex. If a cut vertex exists in a graph, then it must be adjacent to at least two edges, that is, it is contained in the intersection of edges of a graph. Thus, a cut vertex in a graph can be treated as a knot whose removal increases the number of connected components of the graph, as a graph is also a hypergraph. It is also observed that there are hypergraphs in which the removal of a vertex does not increase its components, but the removal of some knots increases its components. That is, removing some vertices or entire vertices from the intersection of intersecting hyperedges in a hypergraph may increase its connected components. Thus, the cut knot is defined in a hypergraph instead of a cut vertex.

It is to be noted that the removal of a vertex or subset of the vertex set in a hypergraph can be done in two different ways ^[4]. One way of doing this is by strong vertex deletion, and another is by weak vertex deletion. The strong vertex deletion of a vertex or subset of a vertex set removes the vertex and all the edges that are incident to the vertex from the hypergraph, while the weak vertex deletion, removes the vertex from the vertex set and from all those edges which contain the vertex. It is observed that the weak deletion of a vertex or subset of a vertex set from a hypergraph may not increase the number of connected components of the hypergraph unless the vertex or subset of vertices is contained in a knot or the points are isolated vertices. So, its significance is less important while studying multi-adic relationships such as in hypergraphs. Thus, the strength of a point in a hypergraph can be determinable if and only if the vertex or subset of vertices is present in the knots, which are a non-empty subset of the intersections of some finite hyperedges. This motivates us to define the strength of knots, which is intuitively equivalent to the strength of a vertex in a graph. Thus, the strength of a knot in a hypergraph is defined as the increase in the number of connected components in the hypergraph upon the removal of the knot from the hypergraph. This notion further changes the dimension of perceiving the different concepts of hypergraphs such as cut knots, cycles, separability, and non-separability of hypergraphs, etc.

Modelling is one of the most commonly used tools for forecasting issues related to the epidemic situation in society. It is a topical problem to develop imitation models of complex systems such as the process of spreading infection ^[5]. The graphical representations and models that are produced by the results of graph theory and hypergraph theory are used in diverse fields and always play a very significant role in the smooth functioning of the world. In fact, the concepts of graphs and hypergraphs can be used to articulate real-life problems and could be beneficial. Considering the recent pandemic in the world, it is the most appropriate way to exercise the graph and hypergraph theoretical models with theoretical as well as practical aspects to control such an unprecedented epidemic. Graph-based modelling and analysis of the COVID-19 virus have been shown to be of great importance and could improve our capacity for anticipating epidemic patterns and developing effective intervention strategies ^[6,7]. However, graphs do not natively capture the multi-way relationships, which do not fully represent the realistic cases where people meet in groups like the market, a workplace, a social setting, etc. ^[8]. A hypergraph is a generalization of graphs that preserves multi-adic relationships and thus becomes a more natural modelling tool for studying multi-adic relationships, such as during the recent pandemic caused by the SARS-CoV-2 virus outbreak. As hyperedges can be used to record higher-order interactions, they yield a more faithful and flexible model that could be beneficial and would be able to deliver a greater understanding of disease dynamics and produce better public health ^[9]. This prompted us to present a hypergraph model that could be used to aid decision-making in the tracing of infected individuals and to manage or control the spread of infectious disease in real-time by using the concept of a knot and the strength of the knot.

The structure of this paper can be summarized as follows: In Section 2, basic terms and terminologies are discussed, and the key concepts of knot strength, knot hypercycle, and cyclic hypergraph are defined. Section 3 begins with the notion of cut knot and separability of hypergraphs, and some results are established therein. In Section 4, an algorithm is introduced to obtain a hypertree from a given strength profile, and to accomplish the algorithm, an illustrative example is discussed. We also introduced an application of the strength of knots and cut knots in Section 5 towards the management of the spread of infectious diseases by creating an artificial problem. The article ends with a concluding section.

2.   Basic definitions and notations

As given by Berge ^[10], a hypergraph $H = (V, E)$ is an ordered pair, where $V = \{v_1, v_2, \cdots, v_n\}$ is a finite set whose elements are known as vertices, and $E = \{e_1, e_2, \cdots e_m\}$ is a collection of non-empty subset of $V$. The members of $E$ are known as hyperedges. The order of a hypergraph $H$ is defined as the cardinality of the vertex set $V$, that is $|V|$; and its size is defined as the cardinality of the edge set $E$, that is $|E|$. Any two vertices in a hypergraph are said to be adjacent if there is a hyperedge containing both of the vertices. In particular, if $\{x\}$ is an hyperedge then, $x$ is adjacent to itself. Any two hyperedges in a hypergraph are said to be incident if their intersection is not empty. If the family of hyperedges satisfies $i\neq j \Longleftrightarrow e_i\neq e_j$, we say that $H$ is without repeated hyperedge and if $e_i\subset e_j\Rightarrow i = j$, then we call $H$ is Sperner family or simple hypergraph. In this paper, all hypergraphs are considered to be simple hyperegraph, and occurrence of repeated hyperedges does not arise. For more general information on hypergraph, we refer ^[10,11,12] and for graphs, we refer ^[13].

Definition 2.1. ^[3] A knot $K$ in a hypergraph $H = (V, E)$ is a non-empty subset of the intersections of some intersecting hyperedges. In other words, if $H = (V, E)$ is a hypergraph and $K$ is a knot, then $K \subseteq \cap e_i\neq \emptyset$ for some intersecting hyperedges $e_i$, $i = 1, 2, \cdots, k$ and $k \geq 2$. In particular, if $K = \cap e_i$, then $K$ is called an entire knot.

Note that, if $C$ is a collection of entire knots, then $(C, \subset)$ is a poset. Thus an entire knot $K$ in a hypergraph $H$ is said to be a maximal knot, if there doesnot exists a knot $K'$ in $H$ such that $K\subset K'$.

Definition 2.2. ^[14] Let $H = (V, E)$ be a hypergraph. By a hyperpath or simple point hyperpath between two distinct vertices $v_1$ and $v_n$ in $V$, we mean a sequence $v_1e_1v_2e_2\cdots v_{n-1}e_{n-1}v_n$ of vertices and hyperedges having the following properties:

$(1)$ $n$ is a positive integer;

$(2)$ $v_1, v_2, \cdots, v_n$ are distinct vertices;

$(3)$ $e_1, e_2, \cdots e_n$ are hyperedges (not necessarily distinct);

$(4)$ $v_k, v_{k+1}\in e_k$ for $k = 1, 2, \cdots, n-1$.

Definition 2.3. ^[14] A hypercycle in a hypergraph $H = (V, E)$ on a vertex $v_1$ is a sequence $v_1e_1v_2e_2\cdots v_{n-1}e_{n-1}v_ne_nv_1$, having the following properties:

$(1)$ $n$ is a positive integer

$(2)$ $v_1e_1v_2e_2\cdots v_{n-1}e_{n-1}v_n$ is a $v_1-v_n$ hyperpath;

$(3)$ at least one of the hyperedges $e_1, e_2, \cdots e_{n-1}$ is distinct from $e_n$;

$(4)$ $v_k, v_{k+1}\in e_k$ for $k = 1, 2, \cdots, v_{n-1}$.

We note that hyperpath is also defined by Rahman et al. ^[3] as given below.

Definition 2.4. ^[3] In a hypergraph $H = (V, E)$, a knot-hyperpath between two vertices $v_1$ and $v_n$ is an alternating sequence of knots and hyperedges of the following type:

where $K_i \subseteq (e_i\cap e_{i+1})\smallsetminus (\cup_{t = 1}^{i-1}K_t)$, with $i = 1, 2, \cdots, n-1, v_1 \in e_1, v_n \in e_n$ and $e_i$'s are distinct hyperedges.

If $K_i = e_i\cap e_{i+1}$ for all $i = 1, 2, \cdots, n-1$, then the knot-hyperpath is called the entire knot-hyperpath. Here, $n$ is called the length of the knot-hyperpath.

Definition 2.5. ^[3] Two knot-hyperpaths

and

of the same length of a hypergraph $H = (V, E)$ are called equivalent or isomorphic if

$(1)$ $e_i\cap e'_i\neq \emptyset$, for all $i = 1, 2, \cdots, n$.

$(2)$ $K_i \cap K'_i \neq \emptyset$, for all $i = 1, 2, \cdots, n-1$.

Definition 2.6. A hypergraph $H = (V, E)$ is said to be connected hypergraph if, for any two distinct vertices $v_i$ and $v_j$ in $H$, there exists a knot hyperpath joining them.

Definition 2.7. Strength of a vertex $v$ in a hypergraph $H = (V, E)$ is defined as the increase in the number of connected components upon the removal of the vertex $v$ from the hypergraph. Removal of vertex means the weak deletion of vertex $v$ from $H$. We denote it as $St(v)$, and read it as strength of the vertex $v$ in hypergraph $H = (V, E)$.

Definition 2.8. Strength of a knot $K$ in a hypergraph $H = (V, E)$ is defined as the increase in the number of connected components upon the removal of the knot $K$ from the hypergraph. The removal of the knot $K$ means the weak deletion of all vertices present in the knot $K$ from $H$. We denote it as $St(K)$, and read it as strength of the knot $K$ in the hypergraph $H = (V, E)$.

The following is an illustrative example:

Example 2.1. Consider the hypergraph $H = (V, E)$ with the vertex set $V = \{v_i | i = 1, 2, \cdots, 20\}$ and edges $E = \{e_1, e_2, \cdots, e_8\}$ such that

$e_1 = \{v_1, v_2, v_3, v_4\}, \, \, \, e_2 = \{v_3, v_4, v_5, v_6, v_7\}, \, \, \, e_3 = \{v_6, v_8, v_9, v_{10} \},$

$e_4 = \{v_3, v_5, v_{11}, v_{12} \}, \, \, \, e_5 = \{v_{11}, v_{12}, v_{13}\}, \, \, \, e_6 = \{v_{11}, v_{12}, v_{14}, v_{15}, v_{16}\},$

$e_7 = \{v_9, v_{10}, v_{11}, v_{20}\}, \, \, \, \text{and} \, \, \, e_8 = \{v_{15}, v_{18}, v_{19}\}.$ (see Figure 1)

We notice that:

● There are 13 possible knots, among these eight are entire knots. In particular $K_1 = e_1\cap e_2 = \{v_3, v_4\}, K_2 = e_1\cap e_4 = e_1\cap e_2\cap e_4 = \{v_3\}, K_3 = e_2\cap e_4 = \{v_3, v_5\}, K_4 = e_2\cap e_3 = \{v_6\}, K_5 = e_3\cap e_7 = \{v_9, v_{10}\}, K_6 = e_5\cap e_7 = e_6\cap e_7 = e_4\cap e_7 = e_4\cap e_5\cap e_7 = e_4\cap e_5\cap e_6\cap e_7 = \{v_{11}\}$, $K_7 = e_4\cap e_5 = e_4\cap e_6 = e_5\cap e_6 = e_4\cap e_5\cap e_6 = \{v_{11}, v_{12}\}$ and $K_8 = e_6\cap e_8 = \{v_{15}\}$ are entire knots.

● On removal of any vertex or subset of vertex set $V$ not contained in knots does not change the number of connected components. For instance, the removal of vertex $v_2$ does not change the number of connected components of $H$. As discussed earlier, in a hypergraph the removal of vertex (weak deletion) is meaningful in order to define the strength, if it is contained in a knot.

● It can be observe that the removal of any knot which is not an entire may not increase the number of connected components, for instance, $K_1' = \{v_4\}\subseteq e_1\cap e_2$. Thus, its significance is less important in this study. Hence, stating strength of a knot from here onwards will mean the strength of an entire knot, unless stated.

● The strength of the knot $K_1$ is the increase in the connected components in $H$ upon the removal of the knot $K_1$, that is, $2-1 = 1$. Similarly, the strengths of the knots $K_2, K_3, K_4, K_5, K_6, K_7$, and $K_8$ are 0, 0, 0, 0, 0, 2, and 1, respectively.

● In the above hypergraph it can be verified that the knot $K_2\subsetneq K_1$ and also $St(K_2) < St(K_1)$. In general for any knots $K\subseteq K'$ in a hypergraph, $St(K)\leq St(K')$.

Several special types of hypergraph cycles have been defined and studied in the literature ^[10,15,16]. Our definition is based on the entire knot hyperpath.

Definition 2.9. ^[3] Suppose that $H = (V, E)$ is a hypergraph and $G = (V, F)$ is a graph over the same vertex set $V$. We say that G is a host graph of $H$ if each hyperedge $e_i\in E$ induces a connected subgraph in $G$.

Definition 2.10. An entire knot hyperpath

in a hypergraph $H = (V, E)$ is said to be an entire knot hypercycle or simply hypercycle if $e_1 = e_n$ and $k\geq 3$.

It is to be noted that if $P = \{v_1\}e_1K_1e_2K_2e_3\cdots e_{n-1}K_{n-1}e_n\{v_n\}$ is a hypercycle, then $v_1, v_n\in e_1 = e_n$ and there is a possibility that $v_1$ and $v_n$ may coincide.

Remark 2.1. If a hypergraph $H = (V, E)$ contains a knot hypercycle $C$, then every host graph $G$ of $H$ must contain a cycle, which is an induced subgraph of the host graph $G$.

Definition 2.11. A hypergraph $H = (V, E)$ is said to be a cyclic hypergraph if $H$ itself is an entire knot hypercycle, that is, there exist an entire knot hypercycle

such that $e_1, e_2, \cdots, e_{n-1}$ are the only hyperedges of the hypergraph $H$. Equivalently, if there exist a permutation $p$ on $E$ such that

is an entire knot hypercycle, then $H$ is called a cyclic hypergraph. Note that $K_j = p(e_j)\cap p(e_{j+1})$, $j = 1, 2, ..., n-1$ are entire knots of $H$.

As an illustration to the above definitions we present the following example

Example 2.2. Consider that $H = (V, E)$ a hypergraph (see Figure 2), where the vertex set $V = \{v_i | i = \; 1, 2, \cdots, 50\}$ and hyperedges $E = \{e_1, e_2, \cdots, e_9\}$ such that

$e_1 = \{v_1, v_2, v_3, v_4, v_5\}, \, \, \, e_2 = \{v_3, v_6, v_7, v_8, v_9, v_{15}, v_{16}, v_{17}, v_{18}\},$

$e_3 = \{v_{16}, v_{17}, v_{18}, v_{25}, v_{26}, v_{30}, v_{31}\}, \, \, \, \, e_4 = \{v_{30}, v_{31}, v_{36}, v_{37}, v_{38}, v_{39}, v_{40}, v_{42}\},$

$e_5 = \{v_2, v_4, v_5, v_{10}, v_{11}, v_{12}, v_{13}, v_{14}\}, \, \, \, e_6 = \{v_{14}, v_{19}, v_{20}, v_{21}, v_{22}, v_{23}, v_{24}, v_{29}\},$

$e_7 = \{v_{32}, v_{33}, v_{34}, v_{35}, v_{41}, v_{45}, v_{46}, v_{47}, v_{48}\}, \, \, \, \, e_8 = \{v_{24}, v_{27}, v_{28}, v_{29}, v_{32}, v_{33}\} \text{and}$

$e_9 = \{v_{40}, v_{42}, v_{43}, v_{44}, v_{45}, v_{46}, v_{47}, v_{48}, v_{49}, v_{50}\}.$

We notice that,

● $H = (V, E)$ is a hypergraph and considering the mapping $\psi: E\longrightarrow E$, defined by $\psi(e_1) = e_1, \psi(e_2) = e_5, \psi(e_3) = e_6, \psi(e_4) = e_8, \psi(e_5) = e_7, \psi(e_6) = e_9, \psi(e_7) = e_4, \psi(e_8) = e_3, \psi(e_9) = e_2$. Then, $\psi$ is a permutation on $E$, and it can be easily verified that, $\{v_1\}\psi(e_1)K_1\psi(e_2)K_2\psi(e_3)K_3\psi(e_4)K_4\psi(e_5)K_5 \psi(e_6)K_6\psi(e_7)K_7\psi(e_8)K_{8}\psi(e_9)K_9\psi(e_1)\{v_1\}$ is an entire knot hyperpath and hence $H$ is a cyclic hypergraph. It can be confirmed from its pictorial representation also (see Figure 3).

Definition 2.12. A hypergraph which does not contain a knot hypercycle is called as a cycle free hypergraph.

A hypergraph $H = (V, E)$ is said to be union of two hypergraph $H_1 = (V_1, E_1)$ and $H = (V_2, E_2)$ if $V = V_1\cup V_2$ and $E = E_1\cup E_2$. Now if a hypergraph can be expressed as the union of some cyclic subhypergraphs, then the graph can be termed as circuit.

Remark 2.2. Defining cyclic hypergraph in terms of a permutation on the set of edges $E$ of hypergraph $H = (V, E)$ could be an interesting topic for investigation in the sense that it can be linked with the notion of permutation group. As a sequel, we would like to explore how it is inter-linked with group theory.

3.   Separable and non-separable hypergraphs

In this section, we generalised the notion of separable and non-separable graphs to hypergraphs and proved some results that are already exists in graph theory to hypergraph theory.

A vertex in a hypergraph is said to be a "cut vertex" if the weak deletion of the vertex increases the number of connected components of the hypergraph ^[17]. Generalising it, we define a cut knot in similar fashion, and later on, we present necessary and sufficient conditions for a hypergraph to be separable and non-separable.

Definition 3.1. Let $H=(V, E)$ be a connected hypergraph. Then an entire knot $K$ of $H$ is said to be a cut knot if the removal the knot $K$ from the hypergraph $H$ disconnects the hypergraph. Note that, the removal here means weak deletion of the knot $K$ from the hypergraph.

Remark 3.1. In a connected hypergraph $H = (V, E)$, a knot $K$ is said to be cut knot, if $c(H) < c(H-K)$, where $c(H)$ is the number of connected components of $H$ and $c(H\smallsetminus K)$ is the number of connected components of $H\smallsetminus K$ upon the removal of the knot $K$ from $H$.

Definition 3.2. A connected hypergraph $H = (V, E)$ is said to be separable hypergraph if there exists atleast one entire knot $K$ in $H$ such that its removal disconnects the hypergraph, that is, if there exist a cut knot $K$ in $H$.

All other hypergraphs will be called as non-separable hypergraph.

Example 3.1. Example 2.1 is a separable hypergraph, since $H$ has cut knot. For instance consider the entire knot $K = e_4\cap e_6 = \{ v_{11}, v_{12}\}$, then on removal of the knot $K$ disconnect the hypergraph into 3 connected components. Whereas Example 2.2 is not a separable hypergraph since there does not exist any cut knot.

Lemma 3.1. ^[3] There exists at least one host graph $G$ of the hypergraph $H = (V, E)$ in which the induced subgraph obtained from any two equivalent knot-hyperpaths never forms a cycle.

Remark 3.2. ^[3] If the induced subgraph obtained from the vertex set of two knot-hyperpaths joining the same vertices of any host graph of a hypergraph always produces a cycle, then the knot hyperpaths are not equivalent.

Theorem 3.2. ^[3] Suppose that H is a connected hypergraph, which is a hypertree. Then, any entire knot hyperpaths having the same length and connecting any two vertices are equivalent.

We note that a hypertree is defined in terms of the host graph of a hypergraph. A hypertree is a hypergraph that admits a host graph, which is a tree ^[18].

Lemma 3.3. A cycle free connected hypergraph is a hypertree.

Proof. Let $H = (V, E)$ be a cycle free connected hypergraph.

Since, $H$ is a connected hypergraph, there exists a knot hyperpath joining any two vertices. Let $u$ and $v$ be any two vertices in $H$ and let $P = \{u\}e_1K_1e_2K_2...K_{n-1}e_n\{v\}$ be a knot hyperpath joining the vertices $u$ and $v$. Since, the hypergraph $H$ is cycle free, therefore, any other knot hyperpath of the same length joining the vertices $u$ and $v$ must be isomorphic to $P$. That is, all the entire knots hyperpath of same length joining $u$ and $v$ must be isomorphic and hence, H is a hypertree.

Remark 3.3. It is to be noted that there are hypertrees which allow point hypercycle in view of Definition 2.3, but cycle free according to Definition 2.10. For example, if $V = \{v_1, v_2, \cdots, v_7\}$ and $E = \{e_1, e_2, e_3\}$, where $e_1 = \{v_1, v_2, v_3, v_4\}$, $e_2 = \{v_3, v_4, v_5, v_6\}$, and $e_3 = \{v_3, v_4, v_6, v_7\}$, then $H = (V, E)$ is a hypetree (Figure 4). But, it contains a point hypercyle given by $C = v_3e_1v_4e_2v_6e_3v_3$. This shows the significance of Lemma 3.3 and also emphasis the importance of knot and knot hyperpath in a hypergraph.

Proposition 3.4. Any cycle free connected hypergraphs are separable. In particular, every hypertree is separable.

Proof. Let $H = (V, E)$ be a cycle free connected hypergraph. We need to show that $H$ is separable. Let $v_1, v_2\in V$. Since $H$ is connected, there exists a path

such that $K_i, 1\leq i\leq n-1$ are entire knots. Since $H$ is cycle free, the path $P_1$ is unique upto isomorphism. We claim that for each $i$, the knot $K_i$ is a cut knot. If not, there exists a $i_0$, such that removal of $K_{i_0}$ does not disconnect the hypergraph. That is, even after the weak deletion of the knot $K_{i_{0}}$, the newly formed hypergraph is connected, and we shall get another entire knot hyperpath

such that $K_{i_{0}} \cap K'_{i_{0}} = \emptyset$. Hence $P_1$ and $P_2$ are two knot hyperpaths which are not equivalent, a contradiction.

Proposition 3.5. A cyclic hypergraph are not separable.

Proof. Let $H$ be a cyclic hypergraph, then by definition there exists a permutation $p$ on edge set $E = \{e_1, e_2, \cdots, e_m\}$ such that,

is an entire knot hypercycle. Clearly, $K_i$ for all $i$ are the only entire knot of the hypergraph and from schematic diagram of the hypercycle (see Figure 5), removal of any entire knot, does not disconnects the hypergraph $H$. Hence no entire knots are cut knots. Hence $H$ is non-separable.

As a consequence of the above theorem, we have the following result.

Remark 3.4. No acyclic hypergraph are non-separable, that is, every acyclic hypergraph are separable, because, if there exist an acyclic hypergraph $H$ which is non-separable, which implies that $H$ has no cut knot. Therefore strength of each knots are Zero. Thus, the hypergraph $H$ is either cyclic or union of concatenation hypercycles.

Theorem 3.6. A connected non-separable hypergraph with size greater than or equal 3 is a circuit and vice-versa.

Proof. $H = (V, E)$ is a connected non separable hypergraph with size not less than 3 iff the removal of any knot does not disconnects the hypergraph $H$ iff every knot appears in atleast one hypercycle in $H$ iff $H$ is the union of hypercycles iff $H$ is a circuit.

Theorem 3.7. An entire knot $K$ of a connected hypergraph $H = (V, E)$ is a cut knot if there is a pair of distinct vertices $v_1$ and $v_2$ such that $K$ appears in every entire knot hyperpath joining the vertices and vice-versa.

Proof. Let $K$ be a cut knot of $H$ and $v_1, v_2\in V$ be a pair of distinct vertices of $H$ connected by an entire knot hyperpath

such that $K$ appears in $P$. We claim that, $K$ appears in every entire knot hyperpath joining $v_1$ and $v_2$. Since $K$ is cut knot, $c(H\smallsetminus K) > c(H)$, and $v_1$ and $v_2$ are connected in $H$, but not in $H\smallsetminus K$. If possible, there exists another entire knot hyperpath

joining $v_1$ and $v_2$ in which $K$ does not appears in $P'$, then $P'$ is an entire knot hyperpath in $H\smallsetminus K$ joining $v_1$ and $v_2$, which contradicts the fact that $K$ is a cut knot. Hence if $K$ is a cut knot then $K$ appears in every entire knot hyperpath joining distinct vertices in $H$.

Conversely, we assume that $K$ is an entire knot such that $K$ appears in every entire knot hyperpath joining a pair of distinct vertices $v_1, v_2\in V(H)$ in $H$. If $K$ is not a cut knot of $H$, then $c(H\smallsetminus K) = c(H)$. This implies that, the pair of distinct vertices $v_1$ and $v_2$ are connected by an entire knot hyperpath

in $H\smallsetminus K$. Thus, $K$ does not appear in the knot hyperpath $P$ in $H$, a contradiction. Hence, $K$ must be a cut knot.

Theorem 3.8. If $H = (V, E)$ is a connected hypergraph such that the strength of each entire knot is greater than or equal to one, then $H$ is a hypertree. But the converse is not true.

Proof. Let $H = (V, E)$ be a connected hypergraph such that strength of each entire knot is greater than or equal to one. Need to show that, $H$ is hypertree. For this it will be sufficient if we show that $H$ is cycle free. Let

be an entire knot hyperpath joining $v_1$ and $v_2$ in $H$. We claim that every entire knot hyperpath of same length joining $v_1$ and $v_2$ in $H$ is isomorphic/equivalent to $P$. Let us assume that there exists an entire knot hyperpath

joining $v_1$ and $v_2$ in $H$ not isomorphic to $P$. Then there exist an entire knot $K_{i_0}$ appears in $P$ such that removal of $K_{i_0}$ does not disconnects $H$. This implies that $c(H\smallsetminus K) = c(H)$. Thus, $K$ is not a cut knot, that is, $St(K_{i_0}) = 0$, which is a contradiction to our assumption. Hence, $H$ must be a hypertree.

The converse of the theorem is not true, for instance, consider the hypergraph $H = (V, E)$, where $V = \{v_i| i = 1, 2, \cdots 13\}$ and $E = \{e_1, e_2, e_3, e_4\}$ such that $e_1 = \{v_1, v_2, v_3, v_4, v_5, v_6\}, e_2 = \{v_4, v_6, v_7, v_9\}$, $e_3 = \{v_4, v_5, v_8, v_{10}, v_{11}\}$ and $e_4 = \{v_{10}, v_{11}, v_{12}, v_{13}\}$. Clearly, $H$ is a hypertree, but entire knot $K = e_2\cap e_3 = \{v_4\}$, has strength 0 (see Figure 6) given below.

4.   An algorithm to obtain a schematic hypergraph from a given strength profile

In the previous section of the paper, we have shown that all entire knots of a hypergraph having strength greater than or equal to one is a hypertree. With these results, in this part of the section, we would like to present an algorithm to construct a schematic graph which can be treated tentatively as a host graph of the hypergraph, when strength profile of a hypergraph is given. Strength profile is nothing but the set of non-zero non-negative integers representing the strengths of all entire knots of a hypergraph arranged in non-increasing order. The procedure may be as follows: Then, provide an algorithm to construct a hypertree from a schematic host graph of a hypergraph which represents a tree of a hypertree.

$(1)$ Let a connected hypergraph $H$ be given, such that $K = \{K_i | i = 1, 2, \cdots, l\}$ are only entire knots with the strengths profile $S = \{m_1, m_2, \cdots, m_l\}$, respectively.

$(2)$ Choose the entire knot, say $K_1$, with highest strength $m_1$.

$(3)$ The knot $K_1$ with strength $m_1$ on removal from $H$ will disconnects the hypergraph into $m_1+1$ components. Therefore, there exists atleast one vertex in each component which are not adjacent to each other. Thus for $m_1+1$ components we must have atleast $m_1+1$ vertices. Write the vertices $v_1, v_2, \cdots, v_{m_1}, v_{m_{1}+1}$ close to the knot $K_1$ and draw an edge $e_i$ for each $i$, $i = 1, 2\cdots m_{1}+1$ joining the vertices $v_i$, for $i = 1, 2\cdots m_{1}+1$ with knot $K_1$.

$(4)$ Since the strength profile of $H$ are in non-increasing order, the next knot would be $K_2$ with strength $m_2$ which has highest strength among the remaining knots.

$(5)$ The knot $K_2$ with strength $m_2$ will disconnect the hypergraph $H$ into $m_2+1$ components, therefore, there exists atleast one vertex in each components distinct from each other. It is to be noted that, $H$ is connected therefore, a vertex in the $m_2+1$ components must be connected via a vertex from the component of $K_1$ through an edge $e_j$ to $K_2$. Thus, joining an edge with the earlier vertex lead that there are $m_2$ components upon the removal of knot $K_2$. Thus for $m_2$ components we must have atleast $m_2$ vertices. Writing the vertices $v_{m_{1}+2}, v_{m_{1}+3}, \cdots v_{m_1+m_2+1}$ close to the knot $K_2$ and making edges $e_j$, for each $j = m_{1}+2, m_{1}+3 \cdots m_1+m_2+1$ with the vertices $v_i$, for $i = m_1+1, m_1+2, \cdots m_{1}+ m_2+1$ with knot $K_2$.

$(6)$ As the set of knots $K$ is finite, the process has a finite numbers of steps. Continuing step 5 for each knot with their given respective strengths, we obtain a schematic tree of the host graph $G$ of $H$. The graph obtained from the above procedure is a subgraph of the host graph $G$ of $H$.

$(7)$ Stop.

Now, to get the hypertree from the constructed tree (host graph), we may go with the following procedure, which approximately represents the original hypertree. We shall encircle the knots $K_1$ with the vertices $v_i$, $i = 1, 2, \cdots, m_1$, except the vertex which will be included in the hyperedge having non-empty intersection with $K_1$ and $K_2$, that is, we may construct hyperedge $E_i$'s, $i = 1, 2, \cdots m_1$, such that for each $i$, $E_i$ contains $v_i$ and $E_i\cap K_1\neq \emptyset$.

In the next step, we may construct $m_2$ hyperedges, say, $E_{m_1+j}$, $j = 1, 2, .\cdots m_2$ such that $E_{m_1+1}$ contains $v_{m_1}+1$ such that $K_1\cap E_{m_1+2}\neq \emptyset$, $K_2\cap E_{m_1+j+1}\neq \emptyset$, for all $j = 1, 2, \cdots m_2+1$. Continuing the same process for the remaining knots, we obtain the hypertree that we wanted to construct.

The following example is discussed to accomplish the above algorithm.

Example 4.1. Let a connected hypergraph $H$ be given with strength profile $S = \{3, 2, 2, 1, 1\}$ of the entire knots. Let $K = \{K_i|i = 1, 2, \cdots, 5\}$ be the set of all entire knots.

Following step 2, we choose the entire knot $K_1$, with highest strength 3. Since the removal of $K_1$ from $H$ will disconnects the hypergraph $H$ into $4$ component. Therefore, there exists atleast one vertex in each components that are distinct. Write the vertices $v_1, v_2, v_3$, and $v_4$ close to the knot $K_1$ and draw edges $e_1, e_2, e_3, e_4$, joining the vertices with knot $K_1$ as shown in Figure 7a.

Next, we choose the entire knot $K_2$ with strength 2 and following the same procedure as above, $K_2$ with strength $2$ will disconnects the hypergraph $H$ into $3$ component, there exists at least one vertex in each component. Since $H$ is connected therefore the vertex from the components of $K_1$ must be connected with $K_2$ via vertex say $v_4$ and edge $e_5$. Now, write the vertices $v_5, v_6$ close to the knot $K_2$ and making the edges $e_6, e_7$, joining the vertices with knot $K_2$ (see Figure 7b). There are possibilities that the vertex from the components of $K_1$ may be connected with $K_2$ via an edge $e_5$ with some other vertex, we will later show that all possible aspects of construction of the hypergraph are isomorphic. For now let us continue the construction. Now, continuing in similar fashion for each entire knots $K_3, K_4$ and $K_5$ with their given strength 2, 1 and 1 respectively, we have a schematic graph representing a tree (see Figure 7b).

Now encircling $\{v_1, K_1\} = E_1$, $\{K_1, v_2, K_2\} = E_2$, $\{v_3, K_1\} = E_3$, $\{v_4, K_1\} = E_4$, similarly $\{v_5, K_2\} = E_5$, $\{K_2, v_6, K_3\} = E_6$, $\{K_3, v_7, K_4\} = E_7$, $\{K_3, v_8, K_5\} = E_8$, $\{v_9, K_4\} = E_9$ and $\{v_{10}, K_5\} = E_{10}$, we can obtain a hypergraph which is a hypertree as show in Figure 8.

Thus, by assigning the remaining required vertices as per the requirement of the hypergraph to the hyperedges, we can obtain a hypergraph with the given knots and their strengths.

It is to be noted that the hypergraph constructed with the help of the above algorithm gives a notion of the original hypergraph in a broader sense. One may easily derive the original form of hypergrah by a series of flips that is, by swapping the hyperedges/ knots accordingly.

5.   Application of cut-knot in managing spread of an infectious disease

Representing the spread of an infectious disease-causing epidemic as a network and manipulating it with the concept of graph theory is a potent approach to understanding the dynamics of the disease and its critical components. The database results in many mathematical graph-based modelling techniques that attempt to describe the measures, effects, and dynamics of COVID-19 in the literature ^{[6,19,20,21,22]}. However, interactions in a graph are always represented in terms of pairs of objects, which do not fully represent realistic cases like the network of COVID-19 and its spreading, where we may consider the nodes as the people and the linkages as the spreading of the disease in some particular area. Rather, it is more appropriate to exercise the hypergraphs with theoretical as well as practical aspects to control such an unprecedented epidemic. So, the representation of such networks by a hypergraph becomes more appropriate as compared to graphs, where interaction levels happen among the objects in groups. As in ^[8] a collective contagion model is studied, in which the infection only starts spreading within a hyperedge after a certain critical number of infectious neighbours has been reached. The critical number may also depend on the environment and group size, as in the case of knots.

The objective of the study is to support decision-making towards the tracing of infected individual and to manage/control the spread of infectious diseases in real-time. As a preventive measure we remove the person in the sense that the person had to undergo mandatory quarantine. Our approach to modelling such disease management is hypothetical and produced in an artificial environment, where the role of the cut knot introduced in Section 3 plays an important role. The importance of the knot can be determined by the number of connected components associated with the entire knot. Moreover, an entire knot K is said to be a key knot if its strength is at its maximum.

Some terms used in the model are discussed before the construction of the model, is as follows:

Definition 5.1. Active agent and passive agent: A person $p$ in a locality $l$ is said to be an active agent if $p$ is infected with some infectious disease. Whereas, a person $p'$ is said to be a passive agent if he$\backslash$she is not infected with any infectious disease but likely to get infected if no precaution has taken.

Definition 5.2. Primary and secondary vulnerable zones: A locality is said to be a primary vulnerable zone if there is a passive agent who is prone to getting infected by an active agent within the same locality. Whereas, a locality is said to be a secondary vulnerable zone if there is a passive person who is prone to getting infected by an active agent from another locality.

Let $C = \{p_1, p_2, .... p_n\}$ be the set of people living in an area and let $L = \{l_1, l_2, ..., l_m\}$ be the collection of sets of people living in different localities of the area. We say that, two or more localities are linked, if at least one person from both the locality shares the same workplace. We construct a model hypergraph $H = (C, L)$ such that there is no locality with only one person living and there is always some people from a locality who do not go to work and look after their houses. We note that, the entire knots of this hypergraph shall represent the work place of the area. Assuming that no vaccination or medical diagnosis is available for the time being. So, in order to control the spread of the disease within the area or the locality, it will be an ideal approach to isolate or quarantine the active people in the locality, analogously like the initial stage of the Covid-19 pandemic situation as imposing a complete lockdown in the area may result in a loss of economic and social harmony.

Assuming the two possibilities of disease transmission, that is, either the authority or organisation is not aware of the active agents from which localities get affected or the exact location of the first active agent is known by the authority. We provided step by step implementation of the algorithm for the application to control the disease transmission by considering both the case as follows:

$(1)$ Let $p$ be an active agent in the locality $l_1$ and so all other people living in the locality $l_1$ are prone to the disease, and so are passive agents. Thus people living in this locality $l_1$ are vulnerable to getting infected with the disease. Therefore, isolating $p$ and driving mass testing in the locality $l_1$ to detect the active agents if any and allowing them a mandatory quarantine will be an appropriate way to control the transmission of disease within the area.

$(2)$ If no one in the locality $l_1$ except a person $p'$ working in work place $K$ is infected, then there is a possibility that the virus has transmitted in the work place $K$ also and, therefore, the possibility of occurrence of community transmission of the disease could be high. Further, controlling the spread of the disease to other community, it will be an appropriate to isolate the person in the entire work place, that is, removal of the knot $K$ by testing each person in the work place. Now hyperedges/localities linked with the work place $K$ becomes a secondary vulnerable zone, and so driving a mass testing in the secondary vulnerable zones could be an intelligent way to trace the people infected by the disease. With advancement in mobile phone technologies and GPS system, it may soon be possible to track accurately people's movement in real time. Thus, isolating and allowing mandatory quarantine to the infected peoples after testing process and let other people to perform their normal life activities under a good care and surveillance would not impact the economy and social harmony in greater way.

$(3)$ If some more people are found who are infected by the disease, then steps 1 and 2 shall be repeated for newly declared active agents and primary zones. If no new active agent is found, then we may proceed to the next step.

$(4)$ Now, to ensure that the disease has not transmitted to other localities it is necessary to take precautionary testing drive to other localities too as there may be many different work places linked with different numbers of localities in an area. To cope with this situation, we propose a step by step procedure as follows:

(a) List all the entire knot$\backslash$workplace.

(b) Find the strengths of each workplace, which gives the idea of number of connected components of the work place.

(c) Choose the workplace with the same maximum strength. If there are more than one workplace with same maximum strength, then choose the one with greater population density and a larger population.

(d) Drive a mass testing campaign in the localities which are connected with the workplace to trace out the active agent. Even, if no active agent are found during the test, then, for the safety, drive another testing campaign in the workplaces having relatively less strengths.

(e) If active agents are found during the testing process, follow the same procedure as in (1) and (2).

(f) This process of tracing the active agents continues for each localities and workplaces linked with the workplace until and unless, the area is disease free.

To accomplish the above procedure for controlling the transmission of infectious disease, let us consider an artificial modelled hypergraph $H = (C, L)$ represented below in Figure 9. Where, $C = \{p_i: i = 1, 2, \cdots 50\}$ are people living in an area and $L = \{l_i: l = 1, 2, \cdots 10\}$ is the set of localities of the area.

Let $p_9$ be an active agent in the locality $l_1$ and so all other people living in the locality $l_1$, that is, $p_5$, $p_6$, $p_7$, and $p_8$, are passive agent. Thus people living in this locality $l_1$ are vulnerable to get infected with the disease. Therefore, isolating $p_9$ and driving a mass testing in the locality $l_1$ to detect the active agent if any will be an appropriate way to control the transmission of disease within the community. If no one in $l_1$ except $p_6$ is infected, then there is a possibility that the virus has transmitted in the work place $K_1$ with workers $p_5, p_6, p_7$ and, therefore, the possibility of occurrence of community transmission of the disease could be high. Further, to control the spread of the disease to other communities, it will be appropriate to isolate the people in the entire work place, i.e., removal of the knot $K_1 = \{p_5, p_6, p_7\}$. Now hyperedges$\backslash$ localities linked with the work place $K_1$ becomes a secondary vulnerable zone, and so driving a mass testing in the secondary vulnerable zone, i.e., $l_2$ and $l_3$ could be an intelligent way to trace the people infected by the disease nearby. We also notice that some peoples of locality $l_2$ share same work place with the person of locality $l_4$ via the work place $K_3 = \{p_{10}, p_{13}\}$. If any active agent in work place $K_3$ is found, then above procedure shall be followed. Continuing in the similar manner for tracing the active agent if any will be a fruitful and a noble way to maintain social harmony.

Now, to ensure that the disease has not been transmitted to other localities, it is necessary to take precautionary testing drives to other localities like $l_8, l_7, l_6$ and so on. As there may be many different work places linked with different numbers of localities in an area. To cope with this situation, we propose a step by step procedure where the importance of notions of knot and strength play a significantly important role as follows: Observing the model hypergraph above, one can easily determine the strength of each workplaces which are $K_1 = \{p_5, p_6, p_7\}, K_2 = \{p_5, p_6\}, K_3 = \{p_{10}, p_{13}\}, K_4 = \{p_{16}, p_{17}, p_{18}\}, K_5 = \{p_{17}, p_{18}\}$, $K_6 = \{p_{25}, p_{26}\}$, $K_7 = \{p_{48}, p_{49}, p_{50}\}$, and $K_8 = \{p_{35}, p_{36}, p_{37}, p_{38}\}$ and their strengths are 2, 1, 1, 3, 1, 1, 1, and 1 respectively. We find that the key knot is $K_4$. Hence removing or shutting down the work place $K_4$ firstly and driving testing in the entire work place and linked localities will be an ideal approach to managing the spread of disease. It is also to be noted that, the localities that have been screened$\backslash$ tested should be monitored under some appropriate SOP successively. This process of tracing and eliminating the active agents is not sufficient if the situation gets worst rather it is believed that this can be appropriate in the early stage of the outbreak of an infectious disease in a society. This model of hypergraphical structures provides quick and easy solutions that might be computationally difficult but not necessarily suitable for each setting of a disease. We look to the future to suggest how the two fields, hypergraph and epidemiological can be engaged together to meet the most appropriate forecasting model and minimize the deficiency related to the epidemic situation in a society.

6.   Conclusions

By defining the strength of a knot of in hypergraph as the increase in the number of connected components in the hypergraph upon the removal of the knot from the hypergraph, we generalised the notion of a cut vertex to a cut knot. We also introduced the notion of an entire knot hypercycle and generalised several theoretical concepts of hypergraph connectivity from graph theoretic perspective. We establish a necessary and sufficient condition for a knot to be cut knot. Furthermore, a sufficient condition for a hypergraph to be a hypertree is established with respect to the strength of knots. Hypergraphs and hypertrees are extensively applied in different branches of applied sciences, both theoretically and practically, and so to amplify, we provided an algorithm to obtain a hypertree from the known strength profile which could be useful in studying digital image processing purpose and therefore, our investigation will give more future ideas towards the applicability of hypergraphs and hypertrees in many other fields. Lastly, a hypothetical hypergraphs modelling towards an infectious disease management in an artificial setting is studied. In our opinion, the results and algorithms obtained could be useful as important tools in big-data analytic, social networking, theoretical computer science, decision-making, etc.

Acknowledgments

We would like to thank the editors, and the four anonymous reviewers for their constructive comments that have helped to improve the presentation and quality of the paper. The first author was partially supported by UGC, Govt. of India via UGC-Ref.No.:1098/(CSIR-UGC NET DEC.2018).

Conflict of interest

All authors declare no conflicts of interest in this paper.