Lexicographical ordering of hypergraphs via spectral moments

Let $G$ be a simple undirected graph with $n$ vertices and $A$ be the adjacency matrix of $G$. The $d$th order spectral moment of $G$ is the sum of $d$ powers of all the eigenvalues of $A$, denoted by $\mathrm{S}_{d}(G)$ [1]. For two graphs $G_{1},G_{2}$ with $n$ vertices, if $\mathrm{S}_{i}(G_{1})=\mathrm{S}_{i}(G_{2})$ for $i=0,1,2,\ldots,n-1$, then adjacency matrices of $G_{1}$ and $G_{2}$ have the same spectrum. Therefore, $\mathrm{S}_{i}(G_{1})=\mathrm{S}_{i}(G_{2})$ for $i=0,1,2,\ldots$. We write $G_{1}\prec_{s}G_{2}$ ($G_{1}$ comes before $G_{2}$ in an $S$-order) if there exists a $k\in\{1,2,\ldots,n-1\}$ such that $\mathrm{S}_{i}(G_{1})=\mathrm{S}_{i}(G_{2})$ for $i=0,1,2,\ldots,k-1$ and $\mathrm{S}_{k}(G_{1})<\mathrm{S}_{k}(G_{2})$. We write $G_{1}=_{s}G_{2}$, if $\mathrm{S}_{i}(G_{1})=\mathrm{S}_{i}(G_{2})$ for $i=0,1,2,\ldots,n-1$.

In 1987, Cvetković and Rowlinson [2] characterized the first and last graphs in an $S$-order of all trees and all unicyclic graphs with given girth, respectively. Other works on the $S$-order of graphs can be referred to [3, 4, 5, 6, 7, 8]. The $S$-order of graphs had been used in producing graph catalogues [9].

In this paper, the $S$-order of hypergraphs is defined. We characterize the first and last hypergraphs in an $S$-order of all uniform hypertrees and all linear unicyclic uniform hypergraphs with given girth, respectively. And we give the last hypergraph in an $S$-order of all linear unicyclic uniform hypergraphs.

Next, we introduce some notations and concepts for tensors and hypergraphs. For a positive integer $n$, let $[n]=\{1,2,\ldots,n\}$. An $m$-order $n$-dimension complex tensor $\mathcal{A}=\left({a_{i_{1}\cdots i_{m}}}\right)$ is a multidimensional array with $n^{m}$ entries on complex number field $\mathbb{C}$, where $i_{j}\in[n],j=1,\ldots,m$.

Let $\mathbb{C}^{n}$ be the set of $n$-dimension complex vectors and $\mathbb{C}^{[m,n]}$ be the set of $m$-order $n$-dimension complex tensors. For $x=\left({x_{1},\ldots,x_{n}}\right)^{\mathrm{T}}\in\mathbb{C}^{n}$, $\mathcal{A}x^{m-1}$ is a vector in $\mathbb{C}^{n}$ whose $i$th component is

A number $\lambda\in\mathbb{C}$ is called an eigenvalue of $\mathcal{A}$ if there exists a nonzero vector $x\in\mathbb{C}^{n}$ such that

where $x^{\left[{m-1}\right]}=\left({x_{1}^{m-1},\ldots,x_{n}^{m-1}}\right)^{\mathrm{T}}$. The number of eigenvalues of $\mathcal{A}$ is $n(m-1)^{n-1}$ [10, 11].

A hypergraph $\mathcal{H}=(V(\mathcal{H}),E(\mathcal{H}))$ is called $m$-uniform if $|e|=m\geq 2$ for all $e\in E(\mathcal{H})$. For an $m$-uniform hypergraph $\mathcal{H}$ with $n$ vertices, its adjacency tensor is the order $m$ dimension $n$ tensor $\mathcal{A}_{\mathcal{H}}=(a_{i_{1}i_{2}\cdots i_{m}})$, where

Clearly, $\mathcal{A}_{\mathcal{H}}$ is the adjacency matrix of $\mathcal{H}$ when $\mathcal{H}$ is $2$-uniform [12]. The degree of a vertex $v$ of $\mathcal{H}$ is the number of edges containing the vertex, denoted by $d_{\mathcal{H}}(v)$ or $d_{v}$. A vertex of $\mathcal{H}$ is called a core vertex if it has degree one. An edge $e$ of $\mathcal{H}$ is called a pendent edge if it contains $|e|-1$ core vertices. Sometimes a core vertex in a pendent edge is also called a pendent vertex. The girth of $\mathcal{H}$ is the minimum length of the hypercycles of $\mathcal{H}$, denoted by $g(\mathcal{H})$. $\mathcal{H}$ is called linear if any two different edges intersect into at most one vertex. The $m$-power hypergraph $G^{(m)}$ is the $m$-uniform hypergraph which obtained by adding $m-2$ vertices with degree one to each edge of the graph $G$.

In 2005, the concept of eigenvalues of tensors was proposed by Qi [10] and Lim [11], independently. The eigenvalues of tensors and related problems are important research topics of spectral hypergraph theories [13, 14, 15, 16], especially the trace of tensors [16, 17, 18, 19, 20].

Morozov and Shakirov gave an expression of the $d$th order trace $\mathrm{Tr}_{d}(\mathcal{A})$ of a tensor $\mathcal{A}$ [17]. Hu et al. proved that $\mathrm{Tr}_{d}(\mathcal{A})$ is equal to the sum of $d$ powers of all eigenvalues of $\mathcal{A}$ [18]. For a uniform hypergraph $\mathcal{H}$, the sum of $d$ powers of all eigenvalues of $\mathcal{A}_{\mathcal{H}}$ is called the $d$th order spectral moment of $\mathcal{H}$, denoted by $\mathrm{S}_{d}(\mathcal{H})$. Then $\mathrm{Tr}_{d}(\mathcal{\mathcal{A}_{\mathcal{H}}})=\mathrm{S}_{d}(\mathcal{H})$. Shao et al. established some formulas for the $d$th order trace of tensors in terms of some graph parameters [19]. Clark and Cooper expressed the spectral moments of hypergraphs by the number of Veblen multi-hypergraphs and used this result to give the “Harary-Sachs” coefficient theorem for hypergraphs [16]. Chen et al. gave a formula for the spectral moment of a hypertree in terms of the number of some sub-hypertrees [20].

This paper is organized as follows. In Section 2, the $S$-order of hypergraphs is defined. We introduce $4$ operations of moving edges on hypergraphs and give changes of the Zagreb index after operations of moving edges. In Section 3, we give the first and last hypergraphs in an $S$-order of all uniform hypertrees. In Section 4, the expressions of $2m$th and $3m$th order spectral moments of linear unicyclic $m$-uniform hypergraphs are obtained in terms of the number of sub-hypergraphs. We characterize the first and last hypergraphs in an $S$-order of all linear unicyclic uniform hypergraphs with given girth. And we give the last hypergraph in an $S$-order of all linear unicyclic uniform hypergraphs.

For two $m$-uniform hypergaphs $\mathcal{H}_{1},\mathcal{H}_{2}$ with $n$ vertices, if $\mathrm{S}_{i}(\mathcal{H}_{1})=\mathrm{S}_{i}(\mathcal{H}_{2})$ for $i=0,1,2,\ldots,n(m-1)^{n-1}-1$, then adjacency tensors of $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ have the same spectrum. Therefore, $\mathrm{S}_{i}(\mathcal{H}_{1})=\mathrm{S}_{i}(\mathcal{H}_{2})$ for $i=0,1,2,\ldots$. We write $\mathcal{H}_{1}\prec_{s}\mathcal{H}_{2}$ ($\mathcal{H}_{1}$ comes before $\mathcal{H}_{2}$ in an $S$-order) if there exists a $k\in\{1,2,\ldots,n(m-1)^{n-1}-1\}$ such that $\mathrm{S}_{i}(\mathcal{H}_{1})=\mathrm{S}_{i}(\mathcal{H}_{2})$ for $i=0,1,2,\ldots,k-1$ and $\mathrm{S}_{k}(\mathcal{H}_{1})<\mathrm{S}_{k}(\mathcal{H}_{2})$. We write $\mathcal{H}_{1}=_{s}\mathcal{H}_{2}$ if $\mathrm{S}_{i}(\mathcal{H}_{1})=\mathrm{S}_{i}(\mathcal{H}_{2})$ for $i=0,1,2,\ldots,n(m-1)^{n-1}-1$. In this paper, $\mathrm{S}_{i}(\mathcal{H})$ is also written $\mathrm{S}_{i},i=0,1,2,\ldots$. Let $\textbf{H}_{1}$ and $\textbf{H}_{2}$ be two sets of hypergraphs. We write $\textbf{H}_{1}\prec_{s}\textbf{H}_{2}$ ($\textbf{H}_{1}$ comes before $\textbf{H}_{2}$ in an $S$-order) if $\mathcal{H}_{1}\prec_{s}\mathcal{H}_{2}$ for each $\mathcal{H}_{1}\in\textbf{H}_{1}$ and each $\mathcal{H}_{2}\in\textbf{H}_{2}$.

For an $m$-uniform hypergraph $\mathcal{H}$ with $n$ vertices, let $\mathrm{S}_{0}(\mathcal{H})=n(m-1)^{n-1}.$ In [12], the $d$th order traces of the adjacency tensor of an $m$-uniform hypergraph were given for $d=1,2,\ldots,m$.

Next, we introduce $4$ operations of moving edges on hypergraphs and give changes of the Zagreb index after operations of moving edges. The sum of the squares of the degrees of all vertices of a hypergraph $\mathcal{H}$ is called the Zagreb index of $\mathcal{H}$, denoted by $M(\mathcal{H})$ [21]. Let $E^{\prime}\subseteq E(\mathcal{H})$, we denote by $\mathcal{H}-E^{\prime}$ the sub-hypergraph of $\mathcal{H}$ obtained by deleting the edges of $E^{\prime}$.

Transformation 1: Let $e=\{u,v,v_{1},v_{2},\ldots,v_{m-2}\}$ be an edge of an $m$-uniform hypergraph $\mathcal{H}$, $e_{1},e_{2},\ldots,e_{t}$ be the pendent edges incident with $u$, where $t\geq 1$, $d_{\mathcal{H}}(u)=t+1$ and $d_{\mathcal{H}}(v)\geq 2$. Write $e_{i}^{{}^{\prime}}=(e_{i}\setminus\{u\})\bigcup\{v\}$. Let $\mathcal{H}^{{}^{\prime}}=\mathcal{H}-\{e_{1},\ldots,e_{t}\}+\{e^{\prime}_{1},\ldots,e^{\prime}_{t}\}$.

Transformation 2: Let $u$ and $v$ be two vertices in a uniform hypergraph $\mathcal{H}$, $e_{1},e_{2},\ldots,e_{r}$ be the pendent edges incident with $u$ and $e_{r+1},e_{r+2},\ldots,e_{r+t}$ be the pendent edges incident with $v$, where $r\geq 1$ and $t\geq 1$. Write $e_{i}^{{}^{\prime}}=(e_{i}\setminus\{u\})\bigcup\{v\},i\in[r]$, $e_{i}^{{}^{\prime}}=(e_{i}\setminus\{v\})\bigcup\{u\},i=r+1,\ldots,r+t$. If $d_{\mathcal{H}}(v)\geq d_{\mathcal{H}}(u)$, let $\mathcal{H}^{\prime}=\mathcal{H}-\{e_{1},\ldots,e_{r}\}+\{e^{\prime}_{1},\ldots,e^{\prime}_{r}\}$. If $d_{\mathcal{H}}(v)<d_{\mathcal{H}}(u)$, let $\mathcal{H}^{\prime}=\mathcal{H}-\{e_{r+1},\ldots,e_{r+t}\}+\{e^{\prime}_{r+1},\ldots,e^{\prime}_{r+t}\}$.

The $m$-uniform hypertree with a maximum degree of less than or equal to $2$ is called the binary $m$-uniform hypertree. For two vertices $u,v$ of an $m$-uniform hypergraph $\mathcal{H}$, the distance between $u$ and $v$ is the length of a shortest path from $u$ to $v$, denoted by $d_{\mathcal{H}}(u,v)$ [22]. Let $d_{\mathcal{H}}(u,u)=0$. Let $\mathcal{H}_{0},\mathcal{H}_{1},\ldots,\mathcal{H}_{p}$ be pairwise disjoint connected hypergraphs with $v_{1},\ldots,v_{p}\in V(\mathcal{H}_{0})$ and $u_{i}\in V(\mathcal{H}_{i})$ for each $i\in[p]$, where $p\geq 1$. Denote by $\mathcal{H}_{0}(v_{1},\ldots,v_{p})\bigodot(\mathcal{H}_{1}(u_{1}),\ldots,\mathcal{H}_{p}(u_{p}))$ the hypergraph obtained from $\mathcal{H}_{0}$ by attaching $\mathcal{H}_{1},\ldots,\mathcal{H}_{p}$ to $\mathcal{H}_{0}$ with $u_{i}$ identified with $v_{i}$ for each $i\in[p]$ [23]. Let $P_{q}$ be a path of length $q$.

Transformation 3: Let $\mathcal{H}\neq P_{0}^{(m)}$ be an $m$-uniform connected hypergraph with $u\in{V(\mathcal{H})}$. Let $\mathcal{T}$ be a binary $m$-uniform hypertree with $v_{k},v_{n},u_{1},u_{2}\in V(\mathcal{T})$ and $e_{k},e_{k+1}\in E(\mathcal{T})$ such that $d_{\mathcal{T}}(v_{k})=2$, $v_{k},u_{1}\in e_{k},v_{k},u_{2}\in e_{k+1}$, $u_{1},u_{2}\neq v_{k}$, $v_{n}$ be a pendent vertex and $d_{\mathcal{T}}(u_{1},v_{n})>d_{\mathcal{T}}(u_{2},v_{n})$. Let $\mathcal{H}_{1}=\mathcal{H}(u)\bigodot\mathcal{T}(v_{k})$. $\mathcal{H}_{2}$ is obtained from $\mathcal{H}_{1}$ by deleting $e_{k}$ and adding $(e_{k}\setminus\{v_{k}\})\bigcup\{v_{n}\}$.

Transformation 4: Let $\mathcal{H}$ be an $m$-uniform connected hypergraph with $u,v\in{V(\mathcal{H})}$ such that $u\neq v$, $d_{\mathcal{H}}(u)>1$ and $d_{\mathcal{H}}(u)\geq d_{\mathcal{H}}(v)$. Let $\mathcal{T}_{1},\mathcal{T}_{2}$ be two binary $m$-uniform hypertrees, where $|E(\mathcal{T}_{1})|>0$. $\mathcal{H}_{1}$ denotes the hypergraph that results from identifying $u$ with the pendent vertex $u_{0}\in e_{0}$ of $\mathcal{T}_{1}$ and identifying $v$ with the pendent vertex $v_{0}$ of $\mathcal{T}_{2}$. Suppose that $v_{t}\in V(\mathcal{T}_{2})$ is a pendent vertex of $\mathcal{H}_{1}$, let $\mathcal{H}_{2}$ be obtained from $\mathcal{H}_{1}$ by deleting $e_{0}$ and adding $(e_{0}\setminus\{u\})\bigcup\{v_{t}\}$.

In this section, we give the first and last hypergraphs in an $S$-order of all uniform hypertrees.

In [20], the first $3k$th order spectral moments of uniform hypertrees were given. Let $N_{\mathcal{H}}(\widehat{\mathcal{H}})$ be the number of sub-hypergraphs of $\mathcal{H}$ isomorphic to $\widehat{\mathcal{H}}$ and $S_{q}$ be a star with $q$ edges.

Let $\textbf{T}_{q}$ be the set of all $m$-uniform hypertrees with $q$ edges. The following theorem gives the last hypergraph in an $S$-order of all $m$-uniform hypertrees.

Let T be the set of all binary $m$-uniform hypertrees with $q$ edges. We characterize the first few hypergraphs in the $S$-order of all $m$-uniform hypertrees.

Let $P_{3}(\mathcal{H})$ be the set of all sub-hyperpaths length $3$ of an $m$-uniform hypergraph $\mathcal{H}$.

The following theorem gives the first hypergraph in an $S$-order of all $m$-uniform hypertrees.

In this section, the expressions of $2m$th and $3m$th order spectral moments of linear unicyclic $m$-uniform hypergraphs are obtained in terms of the number of sub-hypergraphs. We characterize the first and last hypergraphs in an $S$-order of all linear unicyclic $m$-uniform hypergraphs with given girth. And we give the last hypergraph in an $S$-order of all linear unicyclic $m$-uniform hypergraphs.

Let $\mathcal{H}(\omega)$ be a weighted uniform hypergraph, where $\omega:E(\mathcal{H})\rightarrow\mathbb{Z}^{+}$. Let $\omega(\mathcal{H})=\sum_{e\in E(\mathcal{H})}\omega(e)$ and $d_{v}(\mathcal{H}(\omega))=\sum_{e\in E_{v}(\mathcal{H})}\omega(e)$, where $E_{v}(\mathcal{H}):=\{e\in E(\mathcal{H})|v\in e\}$. Let $C_{n}$ be a cycle with $n$ edges. In [24], the formula for the spectral moments of linear unicyclic $m$-uniform hypergraphs was given.