The Rupture Degree of k-Uniform Linear Hypergraph

Ning Zhao

Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China.

DOI: 10.4236/am.2021.127039                

Abstract

We employ graph parameter, the rupture degree, to measure the vulnerability of k-uniform hypergraph G^k. For the k-uniform hypergraph G^k underlying a non-complete graph G = (V, E), its rupture degree r(G^k) is defined as r(G^k) = max{ω(G^k - X) - |X| - m(G^k - X): X ⊂ V(G^k), ω(G^k - X) > 1}, where X is a cut set (or destruction strategy) of G^k, ω(G^k - X) and m(G^k - X) denote the number of components and the order of a largest component in G^k - X, respectively. It is shown that this parameter can be used to measure the vulnerability of networks. In this paper, the rupture degrees of several specific classes of k-uniform hypergraph are determined.

Keywords

The Rupture Degree, Hypergraph, k-Uniform Linear Hypergraph

1. Introduction

The stability of a communication network, composed of processing nodes and communication links, is of prime importance to network designers. Many graph theoretical parameters have been used in measuring the vulnerability of networks, such as connectivity [1] [2], scattering number [3], tenacity [4], toughness [5] [6] and the rupture degree [7].

A hypergraph is a generalization of a graph in which an edge can join any number of vertices. For a hypergraph $H=\left(V\mathrm{,}E\right)$, $V=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ is a set of elements called vertices, and $E=\left\{e_1\mathrm{,}{e}_2\mathrm{,}\cdots \mathrm{,}{e}_m\right\}$ is a set of nonempty subset of V called edges. If $\left|e_i\right|=k$ for $i=1,2,\cdots ,m$, we call H a k-uniform hypergraph. Clearly, ordinary graphs are referred as 2-uniform hypergraphs. A vertex $v_i\in V$ is said to be incident to an edge $e_j\in E$ if $v_i\in e_j$. Two vertices are said to be adjacent if they are contained in one edge. And two edges are said to be adjacent if their intersection is not empty.

A k-uniform linear hypergraph is a k-uniform hypergraph such that every two edges have at most one common vertex. In this paper, all k-uniform hypergraphs are referred as k-uniform linear hypergraph that each edge has at most two non-1-degree vertices. For a vertex $v_i\in V$, its degree $d\left(v_i\right)$ is the number of edges that contain $v_i$.

For an ordinary graph $G=\left(V\mathrm{,}E\right)$ and an integer $k\ge 3$, the k-uniform hypergraph $G^k$ underlies graph G, denoted by $G^k=\left(V^k\mathrm{,}{E}^k\right)$, whose vertex set

$V^k=V\cup \left({\cup }_{e\in E}\left\{v_{e,1},v_{e,2},\cdots ,v_{e,k-2}\right\}\right)$

and edge set

$E^k=\left\{e\cup \left\{v_{e\mathrm{,1}}\mathrm{,}{v}_{e\mathrm{,2}}\mathrm{,}\cdots \mathrm{,}{v}_{e\mathrm{,}k-2}\right\}\mathrm{<mo>\; ;\; </mo>}e\in E\right\}\mathrm{.}$

Hypergraphs are often used as a model of communication networks, paper index data, etc. The vulnerability of hypergraph is an important topic in graph theory research. Here we employ the rupture degree to measure the vulnerability of hypergraph $G^k$. The rupture degree $r\left(G^k\right)$ is similarly defined as

$r\left(G^k\right)=\max \left\{\omega \left(G^k-X\right)-\left|X\right|-m\left(G^k-X\right):X\subset V\left(G^k\right),\omega \left(G^k-X\right)>1\right\},$

where $X\subset V\left(G^k\right)$ is a cut set (or destruction strategy) of $G^k$, $\omega \left(G^k-X\right)$ and $m\left(G^k-X\right)$ denote the number of components and the order of a largest component in $G^k-X$, respectively. A vertex cut set (or a destruction strategy) X of hypergraph $G^k$ is called r-set (or the optimal destruction strategy) if $r\left(G^k\right)=\omega \left(G^k-X\right)-\left|X\right|-m\left(G^k-X\right)$.

Although this vulnerability parameter of $G^k$ is similar in form as the rupture degree of graph G, the optimal destruction strategy is different between G and $G^k$. For a tree T and hypergraph $T^4$ in Figure 1, the cut sets $\left\{v\right\}$ and $\left\{u_1\mathrm{,}{u}_2\mathrm{,}{u}_3\mathrm{,}{u}_4\right\}$ are the optimal destruction strategy of T and $T^4$, respectively.

Figure 1. The optimal destruction strategies for trees T and T⁴.

In this paper, we determine the rupture degree for some k-uniform hypergraphs such as k-uniform hypercomet $C_{t\mathrm{,}r}^k$, k-uniform hypercycles $C_n^k$, k-uniform hypercomplete $K_n^k$ and complete t-partite k-uniform hypergraph $K_{n_1\mathrm{,}{n}_2,\cdots \mathrm{,}{n}_t}^k$.

Throughout this paper, we use $\lfloor x\rfloor$ for the largest integer not large than x and $\lceil x\rceil$ for the smallest integer not smaller than x. A comet $C_{t\mathrm{,}s}$ is a graph obtained by identifying one end of the path $P_t\left(t\ge 2\right)$ with the center of the star $K_{\mathrm{1,}s}$ and the center is called the center of the comet. Any undefined terminology and notations can be found in [8] [9].

2. The Rupture Degree of Some k-Uniform Linear Hypergraphs

In this section, we will determine the rupture degree of some k-uniform hypergraphs such as k-uniform hypercomet $C_{t\mathrm{,}r}^k$, k-uniform hypercycles $C_n^k$, k-uniform hyper complete $K_n^k$ and complete t-partite k-uniform hypergraph $K_{n_1\mathrm{,}{n}_2,\cdots \mathrm{,}{n}_t}^k$.

Lemma 2.1. Let X be an r-set of k-uniform hypergraph $G^k$. Then $m\left(G^k-X\right)=1$.

If not, assume that $m\left(G^k-X\right)\ne 1$, then $m\left(G^k-X\right)\ge k$. Suppose $C_i$ for $1\le i\le p$ are connected components of $G^k-X$ satisfying $\left|C_i\right|=m\left(G^k-X\right)\ge k$. Now select $v_i\in C_i$ and let $X^{\mathrm{<mo>\; *\; </mo>}}=X\cup \left\{v_i\right\}$ for $1\le i\le p$. Clearly, $\omega \left(G^k-X^{\mathrm{<mo>\; *\; </mo>}}\right)\ge \omega \left(G^k-X\right)+p\left(k-2\right)$ and $m\left(G^k-X^{\mathrm{<mo>\; *\; </mo>}}\right)\le m\left(G^k-X\right)-\left(k-1\right)$. Thus we get

$\begin{array}{l}Sc\left(X^{\mathrm{<mo>\; *\; </mo>}}\right)-Sc\left(X\right)\\ =\omega \left(T^k-X^{\mathrm{<mo>\; *\; </mo>}}\right)-m\left(G^k-X^{\mathrm{<mo>\; *\; </mo>}}\right)-\left|X^{\mathrm{<mo>\; *\; </mo>}}\right|-\left[\omega \left(T^k-X\right)-m\left(G^k-X\right)-\left|X\right|\right]\\ \ge p\left(k-2\right)-p+\left(k-1\right)=p\left(k-3\right)+\left(k-1\right)>0.\end{array}$

This contradicts to the choice of X. So $m\left(G^k-X\right)=1$.n

Theorem 2.2. Let $C_{t\mathrm{,}s}^k$ be k-uniform hypergraph that underlies comet graph $C_{t\mathrm{,}s}$. Then

$r\left(C_{t\mathrm{,}s}^k\right)=\left(s+t-1\right)\left(k-1\right)-\lfloor \frac{t-1}{2}\rfloor -\lceil \frac{t}{2}\rceil -1.$

Proof. We distinguish two cases by the parity of t to complete the proof.

Case 1 t is even.

Suppose X be an r-set of $C_{t\mathrm{,}r}^k$, by Lemma 2.1, we have $m\left(C_{t\mathrm{,}s}^k-X\right)=1$. Thus $\omega \left(C_{t\mathrm{,}s}^k-X\right)\le \left(s+t-1\right)\left(k-1\right)+1-\left|X\right|$. Now we discuss the value of $\omega \left(C_{t\mathrm{,}s}^k-X\right)-\left|X\right|-m\left(C_{t\mathrm{,}s}^k-X\right)$ by $\left|X\right|$.

If $\left|X\right|=\frac{t}{2}$, then $\omega \left(C_{t\mathrm{,}s}^k-X\right)-\left|X\right|-m\left(C_{t\mathrm{,}s}^k-X\right)=\left(s+t-1\right)\left(k-1\right)-t$. If $\left|X\right|\le \frac{t}{2}-1$, then $m\left(C_{t\mathrm{,}r}^k-X\right)\ge k\ge 3$, this contradicts to the choice of X. If $\left|X\right|\le \frac{t}{2}-1$, then we get

$\begin{array}{c}r\left(C_{t,s}^k\right)=\omega \left(C_{t,s}^k-X\right)-\left|X\right|-m\left(C_{t,s}^k-X\right)\\ \le \left(s+t-1\right)\left(k-1\right)+1-2\left|X\right|-1\\ \le \left(s+t-1\right)\left(k-1\right)-t-2\\ <\left(s+t-1\right)\left(k-1\right)-t.\end{array}$

Based on the above argument and the definition of the rupture degree, we have

$\begin{array}{c}r\left(C_{t,s}^k\right)=\omega \left(C_{t,s}^k-X\right)-\left|X\right|-m\left(C_{t,s}^k-X\right)\\ =\left(s+t-1\right)\left(k-1\right)-t\\ =\left(s+t-1\right)\left(k-1\right)-\lfloor \frac{t-1}{2}\rfloor -\lceil \frac{t}{2}\rceil -1.\end{array}$

Case 2. t is odd.

Similar to case 1, we directly get

$\begin{array}{c}r\left(C_{t,s}^k\right)=\omega \left(C_{t,s}^k-X\right)-\left|X\right|-m\left(C_{t,s}^k-X\right)\\ =\left(s+t-1\right)\left(k-1\right)-t-1\\ =\left(s+t-1\right)\left(k-1\right)-\lfloor \frac{t-1}{2}\rfloor -\lceil \frac{t}{2}\rceil -1.\end{array}$

n

Let $s=1,t=n-1$ in Theorem 2.2, we get the rupture degree of k-uniform hyperpath $P_n^k$.

Corollary 2.3. $r\left(P_n^k\right)=\left(n-1\right)\left(k-1\right)-\lfloor \frac{n-2}{2}\rfloor -\lceil \frac{n-1}{2}\rceil -1$ .

Let $s=n-1,t=1$ in Theorem 2.2, we get the rupture degree of k-uniform hyperstar $K_{\mathrm{1,}n-1}^k$.

Corollary 2.4. $r\left(K_{1,n-1}^k\right)=\left(n-1\right)\left(k-1\right)-2$ .

Let $k=2$ in Theorem 2.2, we get the rupture degree of comet $C_{t\mathrm{,}r}$, which is shown in [7].

Corollary 2.5.

$r\left(C_{t\mathrm{,}s}\right)=(\begin{array}{ll}s-\mathrm{1,}\hfill & \text{if}t\text{iseven,}\hfill \\ s-\mathrm{2,}\hfill & \text{if}t\text{isodd}\text{.}\hfill \end{array}$

Theorem 2.6. Let $K_{n_1\mathrm{,}{n}_2,\cdots \mathrm{,}{n}_t}^k$ be k-uniform hypergraph that underlies complete t-partite graph $K_{n_1\mathrm{,}{n}_2,\cdots \mathrm{,}{n}_t}$. Then

$r\left(K_{n_1,n_2,\cdots ,n_t}^k\right)=\left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2\max \left\{n_1,n_2,\cdots ,n_t\right\}-{\displaystyle \underset{i=1}{\overset{t}{\sum }}}{n}_i-1.$

Proof. Suppose $V_1\mathrm{,}{V}_2\mathrm{,}\cdots \mathrm{,}{V}_t$ are the partite sets of $K_{n_1\mathrm{,}{n}_2,\cdots \mathrm{,}{n}_t}$ with $\left|V_i\right|=n_i$ for $i=1,2,\cdots ,t$. Without loss of generality, let $n_1=\max \left\{n_1,n_2\cdots ,n_t\right\}$, then $X=V\left(K_{n_1,n_2,\cdots ,n_t}\right)-V_1$ is a vertex cut of $K_{n_1,n_2,\cdots ,n_t}^k$. And then $\omega \left(K_{n_1,n_2,\cdots ,n_t}^k-X\right)=\left(k-2\right){\displaystyle {\sum }_{1\le i<j\le t}}\left(n_i\times n_j\right)+n_1$, $\left|X\right|={\displaystyle {\sum }_{i=1}^t}{n}_i-n_1$ and $m\left(K_{n_1,n_2,\cdots ,n_t}^k-X\right)=1$. Thus we get

$\begin{array}{l}\omega \left(K_{n_1,n_2,\cdots ,n_t}^k-X\right)-\left|X\right|-m\left(K_{n_1,n_2,\cdots ,n_t}^k-X\right)\\ =\left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+n_1-\left({\displaystyle \underset{i=1}{\overset{t}{\sum }}}{n}_i-n_1\right)-1\\ =\left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2\max \left\{n_1,n_2,\cdots ,n_t\right\}-{\displaystyle \underset{i=1}{\overset{t}{\sum }}}{n}_i-1.\end{array}$

Therefore, we have

$r\left(K_{n_1,n_2,\cdots ,n_t}^k\right)\ge \left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2\max \left\{n_1,n_2,\cdots ,n_t\right\}-{\displaystyle \underset{i=1}{\overset{t}{\sum }}}{n}_i-1.$

On the other hand, based on the fact that for any vertex cut $X^{\prime }$ of $K_{n_1,n_2,\cdots ,n_t}$, there exists a partite set $V_i$ such that $V\left(K_{n_1,n_2,\cdots ,n_t}\right)-V_i\subseteq X^{\prime }$, we have

$\begin{array}{l}\omega \left(K_{n_1,n_2,\cdots ,n_t}^k-X^{\prime }\right)-\left|X^{\prime }\right|-m\left(K_{n_1,n_2,\cdots ,n_t}^k-X^{\prime }\right)\\ =\left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+\left(n_i-\left|X^{\prime }\cap V_i\right|\right)-\left[{\displaystyle \underset{j=1}{\overset{t}{\sum }}}{n}_j-\left(n_i-\left|X^{\prime }\cap V_i\right|\right)\right]-1\\ =\left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2n_i-{\displaystyle \underset{j=1}{\overset{t}{\sum }}}{n}_j-1-2\left|X^{\prime }\cap V_i\right|\\ \le \left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2\max \left\{n_1,n_2\cdots ,n_t\right\}-{\displaystyle \underset{j=1}{\overset{t}{\sum }}}{n}_j-1.\end{array}$

Thus, by the definition of rupture degree we get

$r\left(K_{n_1,n_2,\cdots ,n_t}^k\right)\le \left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2\max \left\{n_1,n_2,\cdots ,n_t\right\}-{\displaystyle \underset{i=1}{\overset{t}{\sum }}}{n}_i-1.$

So we get

$r\left(K_{n_1,n_2,\cdots ,n_t}^k\right)=\left(k-2\right){\displaystyle \underset{1\le i<j\le t}{\sum }}\left(n_i\times n_j\right)+2\max \left\{n_1,n_2,\cdots ,n_t\right\}-{\displaystyle \underset{i=1}{\overset{t}{\sum }}}{n}_i-1.$

Let $t=2$ and $k=2$ in Theorem 2.6, we get the rupture degree of $K_{p\mathrm{,}q}^k$ and $K_{p\mathrm{,}q}$ for $p\ge q$, respectively.

Corollary 2.7. $r\left(K_{p,q}^k\right)=pq\left(k-2\right)+p-q-1$ .

Corollary 2.8. $r\left(K_{p,q}\right)=p-q-1$ .

Theorem 2.9 Let $C_n^k\left(n\ge 3\right)$ be k-uniform hypergraph underlies cycle $C_n$. Then

$r\left(C_n^k\right)=n\left(k-1\right)-\lfloor \frac{n-3}{2}\rfloor -\lceil \frac{n-2}{2}\rceil -4.$

Proof. Let X be an r-set of $C_n^k$, by Lemma 2.1, we know that $m\left(C_n^k-X\right)=1$. Note that for any $v\in X$ we have $C_n^k-\left\{v\right\}=P_{n-1}^k\cup 2\left(k-2\right)K_1$. So $X-\left\{v\right\}$ is an r-set of $P_{n-1}^k$. Combine this with the fact $\omega \left[P_{n-1}^k-\left(X-\left\{v\right\}\right)\right]+2\left(k-2\right)=\omega \left(C_n^k-X\right)$, we get

$\begin{array}{c}r\left(C_n^k\right)=\omega \left(C_n^k-X\right)-\left|X\right|-m\left(C_n^k-X\right)\\ =\omega \left[P_{n-1}^k-\left(X-\left\{v\right\}\right)\right]+2\left(k-2\right)-\left|X\right|-1\\ =\omega \left[P_{n-1}^k-\left(X-\left\{v\right\}\right)\right]-\left|X-\left\{v\right\}\right|+2\left(k-2\right)-2\end{array}$

$\begin{array}{c}=r\left(P_{n-1}^k\right)+2\left(k-2\right)-1\\ =\left(n-2\right)\left(k-1\right)-\lfloor \frac{n-3}{2}\rfloor -\lceil \frac{n-2}{2}\rceil -1+2\left(k-2\right)-1\\ =n\left(k-1\right)-\lfloor \frac{n-3}{2}\rfloor -\lceil \frac{n-2}{2}\rceil -4.\end{array}$

n

Let $k=2$ in Theorem 2.9 get the rupture degree of $C_n$, which is obtained in [7].

Corollary 2.10.

$r\left(C_n\right)=(\begin{array}{ll}-\mathrm{1,}\hfill & \text{if}n\text{iseven,}\hfill \\ -\mathrm{2,}\hfill & \text{if}n\text{isodd}\text{.}\hfill \end{array}$

Theorem 2.11. Let $K_n^k$ be a k-uniform hypergraph of complete graph $K_n$. Then

$r\left(K_n^k\right)=\frac{n\left(n-1\right)}{2}\left(k-2\right)-\left(n-1\right)\mathrm{.}$

Proof. Let X be a cut set of $K_n^k$ and suppose $\left|X\right|=x$. It is not difficult to get $\omega \left(K_n^k-X\right)=x\left(n-x\right)\left(k-2\right)+\frac{x\left(x-1\right)}{2}\left(k-2\right)+1$ and $m\left(K_n^k-X\right)=\frac{\left(n-x\right)\left(n-x-1\right)}{2}\left(k-2\right)+\left(n-x\right)$. Thus we have

$\begin{array}{l}\omega \left(K_n^k-X\right)-\left|X\right|-m\left(K_n^k-X\right)\\ =x\left(n-x\right)\left(k-2\right)+\frac{x\left(x-1\right)}{2}\left(k-2\right)+1\\ -x-\frac{\left(n-x\right)\left(n-x-1\right)}{2}\left(k-2\right)+\left(n-x\right)\\ =\left(k-2\right)\left[-x^2+\left(2n-1\right)x-\frac{n^2-n}{2}\right]-\left(n-1\right).\end{array}$

Let $f\left(x\right)=-x^2+\left(2n-1\right)x-\frac{n^2-n}{2}$ with $1\le x\le n-1$. Note that $f^{\prime }\left(x\right)<0$, the function $f\left(x\right)$ is a monotonically increasing in interval $\left[\mathrm{1,}n-1\right]$. So the maximum value of $f\left(x\right)$ in interval $\left[\mathrm{1,}n-1\right]$ is $f\left(x\right)=f\left(n-1\right)=\frac{n^2-n}{2}$. Thus by the definition of rupture degree we get $r\left(K_n^k\right)=\frac{n\left(n-1\right)}{2}\left(k-2\right)-\left(n-1\right)$.

Acknowledgements

The author would like to thank anonymous reviewers for their valuable comments and suggests to improve the quality of the article. This work was supported by QHFRP 2020-ZJ-920 and the National Science Foundation of China (No. 11761056).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Chartrand, M.S.G. (1969) The Connectivity of Line Graphs. Mathematische Annalen, 182, 170-174. https://doi.org/10.1007/BF01350320
[2]	Lv, A.H. (2008) The Connectivity of a Graph and Its Complement. Discrete Applied Mathematics, 156, 3325-3328. https://doi.org/10.1016/j.dam.2008.05.012
[3]	Zhang, S. and Wang, Z. (2001) Scattering Number in Graphs. Networks, 37, 102-106. https://doi.org/10.1002/1097-0037(200103)37:2<102::AID-NET5>3.0.CO;2-S
[4]	Cozzen, M., Moazzami, D. and Stueckle, S. (1995) The Tenacity of a Graph. Proceedings of Seventh International Conference on the Theory and Applications of Graphs, Wiley, New York, 111-122.
[5]	Chvtal, V. (1973) Tough Graphs and Hamiltonian Circuits. Discrete Mathematics, 5, 215-228. https://doi.org/10.1016/0012-365X(73)90138-6
[6]	Bauer, H.B.D. (2006) Toughness in Graphs: A Survey. Graphs and Combin, 22, 1-35. https://doi.org/10.1007/s00373-006-0649-0
[7]	Li, Y., Zhang, S. and Li, X. (2005) Rupture Degree of Graphs. International Journal of Computer Mathematics, 82, 793-803. https://doi.org/10.1080/00207160412331336062
[8]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. GTM 244, Springer, New York. https://doi.org/10.1007/978-1-84628-970-5
[9]	Berge, C. (1976) Graphs and Hypergraphs. Vol. 6, 2nd Edition. North-Holland Mathematical Library, North Holland, Amsterdam.