Sombor index of uniform hypergraphs

1.   Introduction

A hypergraph, denoted by $\mathcal{H}$, is an ordered pair $(V(\mathcal{H}), E(\mathcal{H}))$, where $V(\mathcal{H})$, called the set of vertices, is a finite set and $E(\mathcal{H})$, called the set of edges, is a collection of subsets of $V$. We call the number of elements in $V(\mathcal{H})$ and $E(\mathcal{H})$ the order and size of $\mathcal{H}$, respectively. For convenience, let $n$ and $m$ denote the order and size of a hypergraph, respectively. A hypergraph is said to be $k$-uniform if $|e| = k$ for all $e\in E(\mathcal{H})$. In particular, we call a $2$-uniform hypergraph a graph. For a hypergraph $\mathcal{H}$, the degree of a vertex $v$ in $V(\mathcal{H})$, denoted by $d_{v}$, is the number of edges in $E(\mathcal{H})$ are incident with $v$. All hypergraphs we consider in this paper are finite and without isolated vertices. For the terminologies and concepts not defined here, we refer the readers to ^[3,4].

In 2021, Gutman ^[7] defined the following new topological index of a graph $G$, called the Sombor index:

It has generated much research due to its wide range of applications, see the papers ^{[1,2,6,10,11,13]}. Sombor index is a vertex degree based topological index defined for graphs and therefore, provides information about the size, shape, and branching of molecular structures. It is utilized in QSAR (quantitative structure-activity relationship) studies.

Hypergraphs find application in chemistry when modeling molecules or chemical reactions involving multiple atoms bonding simultaneously. Unlike graphs, hypergraphs can represent interactions involving more than two atoms, which is particularly relevant for reactions with complex bonding patterns and for capturing molecular properties that arise from multiple atom groupings. Hypergraphs offer a more accurate depiction of certain chemical scenarios, such as transition states in reactions, which involve multiple atoms simultaneously changing their bonding configurations. The lack of a convenient representation for molecules with delocalized polycentric bonds is the main drawback of the structure theory. Therefore, these problems can be resolved by hypergraph representation of the molecules, which is known as molecular hyppergraphs. For more results on topological indices related to hypergraphs, we refer the readers to references ^[5,8,12,14].

In ^[9], Liu et al. collected the existing bounds and extremal results related to the Sombor index and its variants. Recently, Shetty and Bhat ^[12] extended this index to hypergraphs as follows:

Contrasting with the Sombor index of ordinary graphs, the Sombor index of hypergraphs is in its infancy. In this paper, we further research the above Sombor index for hypergraphs. We define the Sombor index of a hypergraph $\mathcal{H}$ by

In particular, if $\mathcal{H}$ is a $k$-uniform hypergraph, then

Clearly, if $\mathcal{H}$ is a $2$-uniform hypergraph, then the Sombor index of $\mathcal{H}$ given by Eq (2) will degenerate to the Sombor index of the graph given by Eq (1). Therefore, the Sombor index we define can be viewed as a generalization of the Sombor index defined by Gutman ^[7].

This paper focuses on the Sombor index for $k$-uniform hypergraphs. In Section 2, we first obtain an upper bound for the Sombor index of a $k$-uniform hypergraph of size $m$. An upper bound of the Sombor index of a $k$-uniform linear hypergraph of order $n$ is given. We also obtain a Nordhaus-Gaddum type result for the Sombor index of $k$-uniform hypergraphs. In Section 3, we focus on $k$-uniform linear hypertrees. We obtain upper and lower bounds of the Sombor index of $k$-uniform hypertrees, and demonstrate the tightness of the bounds

2.   $k$-uniform hypergraphs

In this section, we study the Sombor index of $k$-uniform hypergraphs. We first give an upper bound of the Sombor index of $k$-uniform hypergraphs.

Theorem 1. Let $\mathcal{H}$ be a $k$-uniform hypergraph of size $m$. Then

Moreover, the equality holds if and only if $n\geq m+k-1$ and every edge of $\mathcal{H}$ contains $(k-1)$ fixed elements in $V(\mathcal{H})$.

Proof. It is sufficient to consider a $k$-uniform hypergraph $\mathcal{H}$ of size $m$ without isolated vertices. So we may assume that $d_v\geq 1$ for any $v\in V(\mathcal{H})$. Since $|e_1\cap e_2|\leq k-1$ for any two edges $e_1$ and $e_2$ in $\mathcal{H}$, we have

for any edge $\{v_1, v_2, \dots, v_k\}\in E(\mathcal{H})$. To obtain the maximum value of $SO(\mathcal{H})$, we may assume that for any edge $\{v_1, v_2, \dots, v_k\}\in E(\mathcal{H})$,

Without loss of generality, assume that $d_{v_1}\geq d_{v_2}\geq\ldots \geq d_{v_k}$. Note that $1\leq d_{v_t}\leq m$ for $1\leq t\leq k$.

We now prove a claim. Let $x_1, \dots, x_k$ be positive integers with $1\leq x_i\leq m$, $x_1\geq\ldots\geq x_k$ and $x_1+\dots+x_k = (k-1)m+1$.

Claim 1. $x_1^k+\dots+x_k^k\leq (k-1)m^k+1$, and the equality holds if and only if $x_1 = \dots = x_{k-1} = m$ and $x_k = 1$.

Proof of Claim 1. Suppose $x_{k-1}\leq m-1$, and $x_k\geq 2$. Let $y_{k-1} = x_{k-1}+1$, $y_k = x_k-1$ and $y_i = x_i$ for $1\leq i\leq k-2$. Let $f(x) = (x+1)^k-x^k$. Then $f'(x) = k(x+1)^{k-1}-kx^{k-1} > 0$. Thus, $f(x_{k-1})-f(x_k-1) > 0$. So

Therefore

a contradiction. □

By Claim 1, we have $d_{v_1}^k+d_{v_2}^k+\dots+d_{v_k}^k\leq(k-1)m^k+1$ for any edge $\{v_1, v_2, \dots, v_k\}\in E(\mathcal{H})$. So

Moreover, we note that the equality holds if and only if $n\geq m+k-1$, and every edge of $\mathcal{H}$ contains $(k-1)$ fixed elements in $V(\mathcal{H})$. □

A hypergraph $\mathcal{H}$ is linear if each pair of edges of $\mathcal{H}$ has at most one common vertex. A Steiner system $S(2, k, n)$ is a $k$-uniform hypergraph on $[n]$, in which every pair of vertices is contained in exactly one edge.

In particular, we have the following bound of the Sombor index for a $k$-uniform linear hypergraph.

Theorem 2. Let $\mathcal{H}$ be a $k$-uniform linear hypergraph of order $n$. Then

Moreover, the equality holds if and only if every pair of vertices of $\mathcal{H}$ is contained in exactly one edge, which is a Steiner system $S(2, k, n)$.

Proof. Since $\mathcal{H}$ is linear, any pair of vertices is contained in at most one edge. Therefore, considering the number of pairs of vertices, we have

and then $m\leq\frac{n(n-1)}{k(k-1)}$. Note that the equality holds if and only if every pair of vertices of $\mathcal{H}$ is contained in exactly one edge. Since $\mathcal{H}$ is linear, we have $d_v\leq \frac{n-1}{k-1}$ for any $v\in V(\mathcal{H})$. Thus

Thus the equality holds if and only if every pair of vertices of $\mathcal{H}$ is contained in exactly one edge, that is a Steiner system $S(2, k, n)$. □

A hypergraph is $r$-regular if every vertex has degree $r$. A $k$-uniform hypergraph $\mathcal{H}$ is complete if $E(\mathcal{H})$ is the collection of all subsets of $k$ elements in $V(\mathcal{H})$. A $k$-uniform hypergraph $\mathcal{H}$ is empty if $E(\mathcal{H})$ is the empty set. For a $k$-uniform hypergraph $\mathcal{H}$, the complement of $\mathcal{H}$, denoted by $\mathcal{\overline{H}}$, is defined to be the $k$-uniform hypergraph whose vertex set is $V(\mathcal{H})$ and whose edges are all subsets of $k$ elements in $V(\mathcal{H})$ do not belong to $E(\mathcal{H})$.

We have the following Nordhaus-Gaddum type result for the Sombor index of $k$-uniform hypergraphs.

Theorem 3. Let $\mathcal{H}$ be a $k$-uniform hypergraph of order $n$. Then

Moreover, the first equality holds if and only if $\binom{n-1}{k-1}$ is even, and both $\mathcal{H}$ and $\mathcal{\overline{H}}$ are $\frac{1}{2}\binom{n-1}{k-1}$-regular $k$-uniform hypergraphs. The second equality holds if and only if $\mathcal{H}$ is complete or empty.

Proof. Let $|E(\mathcal{H})| = m_1$ and $|E(\mathcal{\overline{H}})| = m_2$. Clearly, $m_1+m_2 = \binom{n}{k}$. We first consider the upper bound. By the definition, we have

Therefore

Clearly, the equality holds if and only if $\mathcal{H}$ is complete or empty.

We now consider the lower bound. By the definition of the Sombor index and Jensen's inequality, we have

where the first equality holds if and only if for any $\{v_1, v_2, \dots, v_k\}\in E(\mathcal{H})$, $d_{v_1} = d_{v_2} = \dots = d_{v_k}$, and the second equality holds if and only if $d_{v_1} = d_{v_2} = \dots = d_{v_n}$.

Therefore

By Jensen's inequality again, we have

where the equality holds if and only if $m_1 = m_2$.

Thus

Clearly, the equality holds if and only if $\binom{n-1}{k-1}$ is even and $\mathcal{H}$ and $\mathcal{\overline{H}}$ both are $\frac{1}{2}\binom{n-1}{k-1}$-regular $k$-uniform hypergraphs. □

3.   $k$-uniform linear hypertrees

In this section, we focus on the Sombor index of $k$-uniform linear hypertrees.

In a hypergraph $\mathcal{H}$, an alternating sequence

of vertices and edges satisfying the following three conditions:

${\bf{(i)}}$ $v_1, \dots, v_{q+1}$ are all distinct vertices of $\mathcal{H}$;

${\bf{(ii)}}$ $e_1, \dots, e_{q}$ are all distinct edges of $\mathcal{H}$;

${\bf{(iii)}}$ $v_r, v_{r+1}\in e_r$ for $r = 1, \dots, q$,

is called a path connecting $v_1$ to $v_{q+1}$, and we call $q$ the length of this path. The distance of two vertices $u$ and $v$ in a hypergraph $\mathcal{H}$, denoted by $d_{\mathcal{H}}(u, v)$, is defined as the length of a shortest path connecting them.

A hypergraph is called a hypertree if every pair of vertices is connected by a unique path. An edge of a $k$-uniform hypergraph is called a pendent if it contains at least $k-1$ vertices of degree $1$. Furthermore, a vertex of degree $1$ is called pendent vertex if it is contained in a pendent edge.

We first obtain an upper bound of the Sombor index of $k$-uniform linear hypertrees.

Theorem 4. Let $\mathcal{T}$ be a $k$-uniform linear hypertree of size $m$. Then

Moreover, the equality holds if and only if all edges of $\mathcal{H}$ meet a vertex in $V(\mathcal{H})$.

Proof. By the definition, we have

where the first inequality is obtained by Hölder's inequality. Moreover, we note that the equality holds if and only if all edges of $\mathcal{H}$ meet a vertex in $V(\mathcal{H})$. □

To obtain a lower bound of the Sombor index of $k$-uniform linear hypertrees, the following preparatory work is necessary.

Lemma 1. For $a\geq b\geq l \geq 1$ and $k > 1$, $(a+l)^k+(b-l)^k > a^k+b^k$.

Proof. Let $f(x) = (x+l)^k-x^k$ for $x\geq 0$. Then $f'(x) = k(x+l)^{k-1}-kx^{k-1} > 0$ for $x\geq 0$, where $f'(x)$ denotes the derivative of $f(x)$. Therefore, $f(a) > f(b-l)$, that is, $(a+l)^k+(b-l)^k > a^k+b^k$. □

We now define an operation of moving edges for a linear uniform hypertree containing vertices of degree at least $3$. Let $\mathcal{T}$ be a linear $k$-uniform hypertree containing vertices of degree at least $3$. Taking a pendent vertex $u$ of $\mathcal{T}$, let $v$ be the vertex with $d_v\geq 3$ such that $d_{\mathcal{T}}(u, v)\leq d_{\mathcal{T}}(u, w)$ for any vertex $w$ with $d_w\geq 3$. Let $e = \{v, v_{1}, v_{2}, \dots, v_{k-1}\}$ be an edge such that the path from $u$ to $v$ contains no $e$. Let $\mathcal{T}'$ be the hypertree obtained from $\mathcal{T}$ by replacing $e$ with $\{u, v_{1}, v_{2}, \dots, v_{k-1}\}$. We say that $\mathcal{T}'$ is obtained from $\mathcal{T}$ by moving $e$ from $v$ to $u$.

Clearly, for a linear uniform hypertree containing vertices of degree at least $3$, we can obtain a linear uniform hypertree containing no vertices of degree at least $3$ by a finite number of operations of moving edges.

For convenience, we fix the following notations. For any edge $e$ of a hypertree $\mathcal{T}$ and $v\in e$, define $S_\mathcal{T}(e) = (\sum_{v\in e}d_v^k)^{\frac{1}{k}}$ and $s_\mathcal{T}(e-v) = \sum_{u\in e\setminus v}d_u^k$. For any vertex $v$ of a hypertree $\mathcal{T}$, denote by $\Gamma(v)$ the set of edges incident with $v$ in $\mathcal{T}$.

Lemma 2. Let $\mathcal{T}$ be a linear $k$-uniform hypertree of order $n$ with the minimum Sombor index among all linear $k$-uniform hypertrees of order $n$. Then $d_v\leq 2$ for all $v\in V(\mathcal{T})$.

Proof. Assume that $\mathcal{T}$ is a linear $k$-uniform hypertree of order $n$ containing at least a vertex of degree at least $3$. Taking a pendent vertex $u$ of $\mathcal{T}$, let $v$ be the vertex with $d_v\geq 3$ such that $d_{\mathcal{T}}(u, v)\leq d_{\mathcal{T}}(u, w)$ for any vertex $w$ with $d_w\geq 3$. Let $e_1 = \{u, u_{1}, u_{2}, \dots, u_{k-1}\}$ be the pendent edge containing $u$. Since $d_v\geq 3$, there exists an edge $e_2 = \{v, v_{1}, v_{2}, \dots, v_{k-1}\}$ in $\mathcal{T}$ not contained in the path from $u$ to $v$. Let $\mathcal{T}'$ be the hypertree obtained from $\mathcal{T}$ by moving $e_2$ from $v$ to $u$. Let $e'_2 = \{u, v_{1}, v_{2}, \dots, v_{k-1}\}$ be the edge in $\mathcal{T}'$ corresponding to $e_2$. Clearly $s_\mathcal{T}(e_2-v) = s_{\mathcal{T}'}(e'_2-u)$. We now divide the proof into two cases.

Case 1. $d_{\mathcal{T}}(u, v) = 1$.

Clearly, in this case, $\{u, v\}\subseteq e_1$. By definition,

By Lemma 1, we have $d_v^k+1 > (d_v-1)^k+2^k$. Then

Clearly, for $d_v\geq 3$,

and for $e\in \Gamma(v)$ and $e\neq e_1, e_2$,

Therefore, we have

Case 2. $d_{\mathcal{T}}(u, v)\geq 2$.

By definition, we have

Clearly, for $e\in \Gamma(v)\setminus \{e_2\}$,

Then

Therefore, to show that $SO(\mathcal{T})-SO(\mathcal{T}') > 0$, it is sufficient to prove

where $a = d_v\geq 3$ and $b = s_\mathcal{T}(e_2-v) = s_{\mathcal{T}'}(e'_2-u)$. Since

that is, $a^k > 2^{k+1}+1$, we have

Let $f(x) = (x+2^k-1)^{\frac{1}{k}}-x^{\frac{1}{k}}$ on $x\geq 0$. Clearly $f'(x) > 0$ when $x\geq 0$. Therefore we have

for $b\geq k-1$. This completes the proof. □

We now present a tight lower bound of the Sombor index of $k$-uniform linear hypertrees.

Theorem 5. Let $\mathcal{T}$ be a $k$-uniform linear hypertree of size $m$. Let $q$ and $r$ be two integers satisfying $(k-2)m+2 = (k-1)q+r$ and $0\leq r < k-1$. Then

Moreover, the equality holds if and only if $\mathcal{T}$ has the maximum number of pendent edges among all $k$-uniform linear hypertrees of size $m$, where the degree of every vertex is at most $2$.

Proof. We assume that $\mathcal{T}$ has the minimum Sombor index among all $k$-uniform linear hypertrees of size $m$. By Lemma 2, we have $d_v\leq 2$ for all $v\in V(\mathcal{T})$. Let $E_1$ denote the set of edges with degree sequence $(2, 1, 1, \dots, 1)$ and $E_2$ denote the set of edges with degree sequence $(2, 2, \dots, 2)$.

Claim 1. $\mathcal{T}$ has at most one edge $e$ such that $e\notin E_1\cup E_2$.

Proof of Claim 1. Assume, for a contradiction, that $e_1 = \{u_1, \dots, u_k\}$ with $d_{u_1} = \dots = d_{u_s} = 2$ and $d_{u_{s+1}} = \dots = d_{u_k} = 1$, and $e_2 = \{v_1, \dots, v_k\}$ with $d_{v_1} = \dots = d_{v_t} = 2$ and $d_{v_{t+1}} = \dots = d_{v_k} = 1$. Without loss of generality, we may assume that $2\leq t\leq s\leq k-1$. Since $e_2$ contains at least two vertices of degree $2$, there exists an edge $e_3$ such that $e_3\cap e_2\neq \emptyset$. Assume, without loss of generality, that $e_3\cap e_2 = \{v_t\}$. Let $\mathcal{T}'$ be the hypertree obtained from $\mathcal{T}$ by moving $e_3$ from $v_t$ to $u_{s+1}$. Then

Set $a = s2^k+k-s$, $b = t2^k+k-t$, $c = (s+1)2^k+k-s-1$ and $d = (t-1)2^k+k-t+1$. Note that $a+b = c+d$ and $c > a\geq b > d$. Let $f(x) = x^{\frac{1}{k}}+(l-x)^{\frac{1}{k}}$. Then $f(x)$ is monotonically increasing in the interval $(0, \frac{l}{2})$ and monotonically decreasing in the interval $(\frac{l}{2}, l)$. Therefore, $a^{\frac{1}{k}}+b^{\frac{1}{k}} > c^{\frac{1}{k}}+d^{\frac{1}{k}}$, which implies that $SO(\mathcal{T})-SO(\mathcal{T}') > 0$. Then a contradiction is clear. Thus, the claim holds. □

Since $\mathcal{T}$ has $m$ edges and $d_v\leq 2$ for all $v\in V(\mathcal{T})$, it follows that $\mathcal{T}$ has $m-1$ vertices of degree $2$. Since $km = \sum_{v\in V(\mathcal{T})}d_v$, $\mathcal{T}$ has $km-2(m-1)$ vertices of degree $1$. Recall that $(k-2)m+2 = (k-1)q+r$, where $0\leq r < k-1$. We now consider the following two cases.

Case 1. $r\geq 1$.

In this case, by Claim 1, there exists a unique edge $e$ of $\mathcal{T}$ such that $e\notin E_1\cup E_2$. Then

Case 2. $r = 0$.

In this case, by Claim 1, for any edge $e$ of $\mathcal{T}$, either $e\in E_1$ or $e\in E_2$. Clearly, $q = \frac{(k-2)m+2}{k-1}$. Then

Note that the expression of $SO(\mathcal{T})$ in Case 2 when $r = 0$ is consistent with that of Case 1. Therefore, we obtain the lower bound. Moreover, note that $\mathcal{T}$ has the maximum number of pendent edges in all $k$-uniform linear hypertrees of size $m$ where the degree of every vertex is at most $2$. □

Further, Theorem 5 is also a tight lower bound of the Sombor index of connected $k$-uniform linear hypergraphs.

4.   Conclusions

Different from the definition of the Sombor index given by Shetty and Bhat ^[12], we define the Sombor index for hypergraphs from another perspective. Clearly, it is more suitable for the structures of hypergraphs and can be viewed as a generalization of the Sombor index defined by Gutman ^[7]. We obtain several upper and lower bounds of the Sombor index of uniform hypergraphs. In particular, a comparison of $SO'(\mathcal{H})$ and $SO(\mathcal{H})$ has been listed as Table 1.

Fano plane is the unique hypergraph with 7 edges on 7 vertices in which every pair of vertices is contained in a unique edge. It is easy to see that the results in the table above are the same for a 2-uniform hypergraph. A natural problem is:

Problem 6. What are the bounds of the Sombor index of general hypergraphs?

Author contributions

X. W. Wang: Conceptualization, Investigation, Methodology, Writing-original draft, Writing-review, editing. M. Q. Wang: Conceptualization, Methodology, Supervision, Writing-review, editing.

Acknowledgments

The authors thank two referees whose kind suggestions largely improve the quality of this paper. This work was supported by the Natural Science Foundation of Shandong Province [No. ZR2023QA080] and Yantai university doctoral research start-up fund [No. SX22B208].

Conflict of interest

The authors declare that they have no conflict of interest.