Cored Hypergraphs, Power Hypergraphs and Their Laplacian H-Eigenvalues

Introduction

A natural definition for the Laplacian tensor and the signless Laplacian tensor of a $k$-uniform hypergraph for $k\geq 3$ was introduced in . See Definition 2.2 of this paper. Recently, Hu, Qi and Xie studied the largest Laplacian and signless Laplacian eigenvalues of a $k$-uniform hypergraph, and generalized some classical results of spectral graph theory to spectral hypergraph theory, in particular, when $k$ is even.

One classical result in spectral graph theory is that the largest Laplacian eigenvalue of a graph is always less than or equal to the largest signless Laplacian eigenvalue, and when the graph is connected, the equality holds if and only if the graph is bipartite.

In , it was shown that the largest Laplacian H-eigenvalue of a $k$-uniform hypergraph is always less than or equal to the largest signless Laplacian H-eigenvalue, and when the hypergraph is connected, the equality holds if and only if the hypergraph is odd-bipartite. A $k$-uniform hypergraph is called odd-bipartite if $k$ is even, and the vertex set of the hypergraph can be divided to two parts, such that each edge has odd number of vertices in each of these two parts.

Hu, Qi and Xie generalized cycles in graphs to hypercycles in $k$-uniform hypergraphs. By showing that the largest signless Laplacian H-eigenvalue for a hypercycle is computable and an even-order hypercycle is odd-bipartite, they showed that the largest Laplacian H-eigenvalue of a hypercycle is computable when $k$ is even.

Another classical result in spectral graph theory is that the largest Laplacian eigenvalue of a graph is always greater than or equal to the maximum degree of that graph, plus one. The lower bound is attained if there exists a vertex adjacent to all the other vertices of that graph.

Hu, Qi and Xie showed that when $k$ is even the largest Laplacian H-eigenvalue of a $k$-uniform hypergraph is always greater than or equal to the maximum degree of that hypergraph, plus $\alpha(k)$, where $\alpha(k)>0$ and $\alpha(2)=1$. They showed that the lower bound is attained if the hypergraph is a hyperstar.

When $k$ is odd, the situation is very different. It was shown in that in this case the largest Laplacian H-eigenvalue is always strictly less than the largest signless Laplacian H-eigenvalue, and the lower bound of the largest Laplacian H-eigenvalue is the maximum degree itself, attained by any hyperstar.

The results of raised the interests to study the Laplacian H-eigenvalues of a $k$-uniform hypergraph. Actually, they posed several questions for further research. First, when $k$ is odd, is a hyperstar the only example of a $k$-uniform hypergraph whose largest Laplacian H-eigenvalue is equal to the maximum degree? Second, can we calculate all Laplacian H-eigenvalues for some special $k$-uniform hypergraphs, such as hyperstars and hypercycles? This is useful if one wishes to study the second smallest Laplacian H-eigenvalue (with multiplicity) of a $k$-uniform hypergraph, as the second smallest Laplacian eigenvalue of a graph plays a key role in spectral graph theory .

Motivated by these questions, we study Laplacian H-eigenvalues of some special $k$-uniform hypergraphs in this paper.

With the same way to generalize stars and cycles to hyperstars to hypercycles, we may generalize an arbitrary graph $G$ to a $k$-uniform hypergraphs $G^{k}$. See Definition 2.4 of this paper. We call $G^{k}$ the $k$th power of $G$, hence call it a power hypergraph. In particular, paths are generalized to hyperpaths. We will see that when $k$ is even, a power hypergraph is odd-bipartite. We may conclude this for a broader class of $k$-uniform hypergraphs. We call such hypergraphs cored hypergraphs. See Definition 2.3 of this paper. A power hypergraph is a cored hyoergraph but not vice versa. In particular, we introduce a special subclass of cored hypergraphs, called sunflowers. See Definition 3.1 of this paper. A sunflower is not a power hypergraph in general. We show that when $k$ is even, a cored hypergraph is odd-bipartite. Thus, when $k$ is even, the largest Laplacian H-eigenvalue and the largest signless Laplcian H-eigenvalue of a cored hypergraph is the same. This enhances our understanding on odd-bipartite hypergraphs and their largest Laplacian eigenvalues. We will show that the largest Laplacian H-eigenvalue of an even-order sunflower is computable.

Then, when $k$ is odd, we will show that the largest Laplacian H-eigenvalue of an odd-uniform sunflower, hypercycle and hyperpath is equal to the maximum degree, i.e., $2$. This shows that for a very broad class of hypergraphs, when $k$ is odd, the largest Laplacian H-eigenvalue is equal to the maximum degree of the hypergraph.

Finally, we will compute out all the H-spectra of the class of hyperstars, the hypercycle of size $3$ and the hyperpath of length $3$. This will be useful for research on the second smallest Laplacian H-eigenvalue of $k$-uniform hypergraphs.

For discussion on the eigenvectors of the zero Laplacian and signless Laplacian eigenvalues of a $k$-uniform hypergraph, see . For discussion on eigenvalues of adjacency tensors and the other types of Laplacian tensors of $k$-uniform hypergraphs, see and references therein.

The rest of this paper is organized as follows. Definitions on eigenvalues of tensors and uniform hypergraphs are presented in the next section. Cored hypergraphs and power hypergraphs are introduced there. We discuss in Section 3 some properties on the cored hypergraphs. An even-uniform cored hypergraph has equality for the largest Laplacian and the singless Laplacian H-eigenvalues. Sunflowers are introduced and investigated in Section 3.2. We compute out the largest Laplacian H-eigenvalues of even-uniform sunflowers and prove that they are equal to the maximum degrees, i.e., $2$, for odd-uniform sunflowers. We show in Section 4.1 that the largest Laplacian H-eigenvalues of odd-uniform hypercycles and hyperpaths are equal to the maximum degrees, i.e., $2$. We make a conjecture in Section 4.2 that the largest H-eigenvalues of even-uniform power hypergraphs with respect to the same underlying usual graph are strictly decreasing as $k$ increasing. This conjecture is proved to be true for hyperstars and hypercycles. In Section 5, we compute out all the H-eigenvalues of hyperstars, the hyperpath of length $3$ and the hypercycle of size $3$. Some final remarks are made in the last section.

Preliminaries

In this subsection, some definitions of H-eigenvalues of tensors are presented. For comprehensive references, see and references therein. Especially, for spectral hypergraph theory oriented facts on eigenvalues of tensors, please see .

H-eigenvalues are real numbers, by Definition 2.1. By , we have that the number of H-eigenvalues of a real tensor is finite. By , we have that all the tensors considered in this paper have at least one H-eigenvalue. Hence, we can denote by $\lambda(\mathcal{T})$ as the largest H-eigenvalue of a real tensor $\mathcal{T}$.

For a subset $S\subseteq[n]$, we denoted by $|S|$ its cardinality, and $\mbox{sup}(\mathbf{x}):=\{i\in[n]\;|\;x_{i}\neq 0\}$ is the support of $\mathbf{x}$.

2 Uniform Hypergraphs

In this subsection, we present some essential notions of uniform hypergraphs which will be used in the sequel. Please refer to for comprehensive references.

In this paper, unless stated otherwise, a hypergraph means an undirected simple $k$-uniform hypergraph $G$ with vertex set $V$, which is labeled as $[n]=\{1,\ldots,n\}$, and edge set $E$. By $k$-uniformity, we mean that for every edge $e\in E$, the cardinality $|e|$ of $e$ is equal to $k$. Throughout this paper, $k\geq 3$ and $n\geq k$. Moreover, since the trivial hypergraph (i.e., $E=\emptyset$) is of less interest, we consider only hypergraphs having at least one edge (i.e., nontrivial) in this paper.

For a subset $S\subset[n]$, we denote by $E_{S}$ the set of edges $\{e\in E\;|\;S\cap e\neq\emptyset\}$. For a vertex $i\in V$, we simplify $E_{\{i\}}$ as $E_{i}$. It is the set of edges containing the vertex $i$, i.e., $E_{i}:=\{e\in E\;|\;i\in e\}$. The cardinality $|E_{i}|$ of the set $E_{i}$ is defined as the degree of the vertex $i$, which is denoted by $d_{i}$. Two different vertices $i$ and $j$ are connected to each other (or the pair $i$ and $j$ is connected), if there is a sequence of edges $(e_{1},\ldots,e_{m})$ such that $i\in e_{1}$, $j\in e_{m}$ and $e_{r}\cap e_{r+1}\neq\emptyset$ for all $r\in[m-1]$. A hypergraph is called connected, if every pair of different vertices of $G$ is connected. Let $S\subseteq V$, the hypergraph with vertex set $S$ and edge set $\{e\in E\;|\;e\subseteq S\}$ is called the sub-hypergraph of $G$ induced by $S$. We will denote it by $G_{S}$. A hypergraph is regular if $d_{1}=\cdots=d_{n}=d$. A hypergraph $G=(V,E)$ is complete if $E$ consists of all the possible edges. In this case, $G$ is regular, and moreover $d_{1}=\cdots=d_{n}=d={n-1\choose k-1}$. In the sequel, unless stated otherwise, all the notations introduced above are reserved for the specific meanings.

For the sake of simplicity, we mainly consider connected hypergraphs in the subsequent analysis. By the techniques in , the conclusions on connected hypergraphs can be easily generalized to general hypergraphs.

The following definition for the Laplacian tensor and signless Laplacian tensor was proposed by Qi .

Let $G=(V,E)$ be a $k$-uniform hypergraph. The adjacency tensor of $G$ is defined as the $k$-th order $n$-dimensional tensor $\mathcal{A}$ whose $(i_{1}\ldots i_{k})$-entry is:

Let $\mathcal{D}$ be a $k$-th order $n$-dimensional diagonal tensor with its diagonal element $d_{i\ldots i}$ being $d_{i}$, the degree of vertex $i$, for all $i\in[n]$. Then $\mathcal{L}:=\mathcal{D}-\mathcal{A}$ is the Laplacian tensor of the hypergraph $G$, and $\mathcal{Q}:=\mathcal{D}+\mathcal{A}$ is the signless Laplacian tensor of the hypergraph $G$.

By , zero is always the smallest H-eigenvalue of $\mathcal{L}$ and $\mathcal{Q}$, and we have $\lambda(\mathcal{L})\leq\lambda(\mathcal{Q})\leq 2d$, where $d$ is the maximum degree of $G$.

In the following, we introduce the class of cored hypergraphs.

Let $G=(V,E)$ be a $k$-uniform hypergraph. If for every edge $e\in E$, there is a vertex $i_{e}\in e$ such that the degree of the vertex $i_{e}$ is one, then $G$ is a cored hypergraph. A vertex with degree being one is a cored vertex, and a vertex with degree being larger than one is an intersectional vertex.

Let $G=(V,E)$ be an ordinary graph. For every $k\geq 3$, we can introduce a hypergraph by blowing up the edges of $G$.

Let $G=(V,E)$ be a $2$-uniform graph. For any $k\geq 3$, the $k$th power of $G$, $G^{k}:=(V^{k},E^{k})$ is defined as the $k$-uniform hypergraph with the set of edges being $E^{k}:=\{e\cup\{i_{e,1},\ldots,i_{e,k-2}\}\;|\;e\in E\}$, and the set of vertices being $V^{k}:=V\cup\{i_{e,1},\ldots,i_{e,k-2},\;e\in E\}$.

It is easy to see that the class of power hypergraphs is a subclass of cored hypergraphs. The classes of hyperstars and hypercycles are introduced in . It can be seen that the classes of hyperstars and hypercycles are subclasses of power hypergraphs. Actually, a $k$-uniform hyperstar (respectively hypercycle) is the $k$th power of a star (respectively cycle) graph.

We present in Figure 1 an example of an ordinary graph and its $3$rd and $4$th power hypergraphs.

For completeness, we include the defintiions for hyperstars and hypercycles in Definitions 2.5 and 2.6 respectively.

Let $G=(V,E)$ be a $k$-uniform hypergraph. If there is a disjoint partition of the vertex set $V$ as $V=V_{0}\cup V_{1}\cup\cdots\cup V_{d}$ such that $|V_{0}|=1$ and $|V_{1}|=\cdots=|V_{d}|=k-1$, and $E=\{V_{0}\cup V_{i}\;|\;i\in[d]\}$, then $G$ is called a hyperstar. The degree $d$ of the vertex in $V_{0}$, which is called the heart, is the size of the hyperstar. The edges of $G$ are leaves, and the vertices other than the heart are vertices of leaves.

Let $G=(V,E)$ be a $k$-uniform nontrivial hypergraph. If we can number the vertex set $V$ as $V:=\{i_{1,1},\ldots,i_{1,k-1},\ldots,i_{d,1},\ldots,i_{d,k-1}\}$ for some positive integer $d$ such that $E=\{\{i_{1,1},\ldots,i_{1,k-1},i_{2,1}\},\{i_{2,1},\ldots,i_{2,k-1},i_{3,1}\},\ldots,\{i_{d-1,1},\ldots,i_{d-1,k-1},i_{d,1}\},\{i_{d,1},\ldots,i_{d,k-1},i_{1,1}\}\}$, then $G$ is called a hypercycle. $d$ is the size of the hypercycle.

It is easy to see that a $k$-uniform hyperstar of size $s>0$ has $n=s(k-1)+1$ vertices, a $k$-uniform hypercycle of size $s>0$ has $n=s(k-1)$ vertices, and they are both connected.

Besides hyperstars and hypercycles, power hypergraphs contain hyperpaths. Hyperpaths are power hypergraphs of usual paths. We state it in the next definition.

Let $G=(V,E)$ be a $k$-uniform hypergraph. If we can number the vertex set $V$ as $V:=\{i_{1,1},\ldots,i_{1,k},i_{2,2},\ldots,i_{2,k},\ldots,i_{d-1,2},\ldots,i_{d-1,k},i_{d,2},\ldots,i_{d,k}\}$ for some positive integer $d$ such that $E=\{\{i_{1,1},\ldots,i_{1,k}\},\{i_{1,k},i_{2,2},\ldots,i_{2,k}\},\ldots,\{i_{d-1,k},i_{d,2},\ldots,i_{d,k}\}\}$, then $G$ is a hyperpath. $d$ is the length of the hyperpath.

Figure 2 is an axample of a $3$-uniform hyperpath.

The notions of odd-bipartite and even-bipartite even-uniform hypergraphs are introduced in .

Let $k$ be even and $G=(V,E)$ be a $k$-uniform hypergraph. It is called odd-bipartite if either it is trivial (i.e., $E=\emptyset$) or there is a disjoint partition of the vertex set $V$ as $V=V_{1}\cup V_{2}$ such that $V_{1},V_{2}\neq\emptyset$ and every edge in $E$ intersects $V_{1}$ with exactly an odd number of vertices.

Cored Hypergraphs

Some facts on the H-eigenvalues and H-eigenvectors of the Laplacian tensor of a cored hypergraph is discussed in this section.

In this subsection, we establish some facts that all cored hypergraphs share.

The next lemma says that their H-eigenvectors have special structures.

Proof. By the definition of H-eigenvalues and the fact that $i$ and $j$ are cored vertices, we have

Since $\lambda\neq 1$, we have that $|x_{i}|=|x_{j}|$. Moreover, when $k$ is odd, we see that $x_{i}=x_{j}$. $\Box$

By [14, Theorem 4], we have the following lemma.

Let $G=(V,E)$ be a $k$-uniform hypergraph with its maximum degree $d>0$ and $\mathcal{L}$ be its Laplacian tensor. Then $\lambda(\mathcal{L})\geq d$.

Proof. Suppose that $i$ is a cored vertex of an arbitrary but fixed edge $e\in E$. If $\lambda=1$, then

implies that $\prod_{s\in e\setminus\{i\}}x_{s}=0$. We are done.

In the following, suppose that $\lambda>1$. Then,

When $k$ is odd, $x_{i}^{k-1}\geq 0$. Then the result follows. When $k$ is even, we have $\prod_{s\in e}x_{s}\leq 0$ since $(\lambda-1)x_{i}^{k}=-\prod_{s\in e}x_{s}$. $\Box$

By Lemmas 3.2 and 3.3, we get the next proposition.

By [10, Theorem 5.1], we can get the next proposition.

Let $k$ be even and $G=(V,E)$ be a $k$-uniform cored hypergraph. Let $\mathcal{L}$ and $\mathcal{Q}$ be the Laplacian tensor and signless Laplacian tensor of $G$ respectively. Then $G$ is odd-bipartite, and hence $\lambda(\mathcal{L})=\lambda(\mathcal{Q})$.

Proof. For all $e\in E$, let $i_{e}\in e$ be a cored vertex. Set $V_{1}:=\{i_{e}\;|\;e\in E\}$ and $V_{2}:=V\setminus V_{1}$. Then it is easy to see that $V=V_{1}\cup V_{2}$ is an odd-bipartition (Definition 2.8). Thus, the result follows from [10, Theorem 5.1]. $\Box$

Actually, we can get the next proposition.

Let $k$ be even and $G=(V,E)$ be a $k$-uniform cored hypergraph. Let $\mathcal{L}$ and $\mathcal{Q}$ be the Laplacian tensor and signless Laplacian tensor of $G$ respectively. For every $e\in E$, let $i_{e}\in e$ be a cored vertex.

Proof. The results follow from Definition 2.1 and Proposition 3.1. $\Box$

2 Sunflowers

Obviously, not all cored hypergraphs are power hypergraphs. Among the others, the class of sunflowers is investigated.

Let $G=(V,E)$ be a $k$-uniform hypergraph. If we can number the vertex set $V$ as $V:=\{i_{1,1},\ldots,i_{1,k},\ldots,i_{k-1,1},\ldots,i_{k-1,k},i_{k}\}$ such that the set of edges being $E=\{\{i_{1,1},\ldots,i_{1,k}\},\ldots,\{i_{k-1,1},\ldots,i_{k-1,k}\},\{i_{1,1},\ldots,i_{k-1,1},i_{k}\}\}$, then $G$ is a sunflower.

Note that the sunflower for every positive integer $k$ is unique, in the sense that by a possible renumbering the vertices two $k$-uniform sunflowers are the same. Figure 3 is an example of the $4$-uniform sunflower.

The next proposition finds out the largest H-eigenvalue of the Laplacian tensor of an even-uniform sunflower.

Let $k$ be even and $G=(V,E)$ be the $k$-uniform sunflower. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $G$ is odd-bipartite and $\lambda(\mathcal{L})$ is the unique root of $(\mu-2)-\left(\frac{1}{\mu-1}\right)^{\frac{1}{k-1}}-\left(\frac{1}{\mu-1}\right)^{k-1}=0$ in the interval $(2,4)$.

Proof. Suppose that $V=\{i_{1,1},\ldots,i_{1,k},\ldots,i_{k-1,1},\ldots,i_{k-1,k},i_{k}\}$, and the set of edges is $E=\{\{i_{1,1},\ldots,i_{1,k}\},\ldots,\{i_{k-1,1},\ldots,i_{k-1,k}\},\{i_{1,1},\ldots,i_{k-1,1},i_{k}\}\}$. Let $\mathcal{Q}$ be the signless Laplacian tensor of $G$. By Proposition 3.2, $G$ is odd-bipartite and $\lambda(\mathcal{L})=\lambda(\mathcal{Q})$.

Let $x_{i_{k}}=\alpha>0$, $x_{i_{j,1}}=1$, and $x_{i_{j,2}}=\cdots=x_{i_{j,k}}=\gamma>0$ for all $j\in[k-1]$. Suppose that $\mathbf{x}$ is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $\mu=\lambda(\mathcal{Q})$. By Definition 2.1, we have

By Lemma 3.2, we have $\mu\geq 2$. Thus, the first and the third equalities imply that $\alpha^{k-1}=\gamma$. Hence,

Let $f(\mu):=(\mu-2)-\left(\frac{1}{\mu-1}\right)^{\frac{1}{k-1}}-\left(\frac{1}{\mu-1}\right)^{k-1}$. We have that $f(2)=-2<0$ and

Thus, $f(\mu)=0$ does have a root in the interval $(2,4)$. Since $\mathcal{Q}$ has a unique positive H-eigenvector ([8, Lemmas 2.2 and 2.3]), the equation $(\mu-2)-\left(\frac{1}{\mu-1}\right)^{\frac{1}{k-1}}-\left(\frac{1}{\mu-1}\right)^{k-1}=0$ has a unique positive solution which is in the interval $(2,4)$. Hence, the result follows. $\Box$

The next proposition says that the largest H-eigenvalue of the Laplacian tensor of an odd-uniform sunflower is equal to the maximum degree, ie., $2$.

Let $k$ be odd and $G=(V,E)$ be the $k$-uniform sunflower. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $\lambda(\mathcal{L})=2$.

Thus, $(\lambda(\mathcal{L})-1)w_{i_{j,s}}^{k}=-w_{i_{j,1}}\prod_{t\in\{2,\ldots,k\}}w_{i_{j,t}}$. Hence, $w_{i_{i,2}}=\cdots=w_{i_{j,k}}=:z_{j}$ for all $j\in[k-1]$, since $\lambda(\mathcal{L})\geq 2$ by Lemma 3.2. Let $x:=w_{i_{k}}$, and $y_{j}:=w_{i_{j,1}}$ for all $j\in[k-1]$. Then, we have $y_{j}=(1-\lambda(\mathcal{L}))z_{j}$ if $z_{j}\neq 0$, for all $j\in[k-1]$. Moreover, by Definition 2.1, we have

Thus, either $z_{1}=\cdots=z_{k-1}=:z$ since $k$ is odd, or $(\lambda(\mathcal{L})-2)(1-\lambda(\mathcal{L}))^{k-1}+(1-\lambda(\mathcal{L}))=0$ and $x\prod_{s\in[k-1]}y_{s}=0$.

If $(\lambda(\mathcal{L})-2)(1-\lambda(\mathcal{L}))^{k-1}+(1-\lambda(\mathcal{L}))=0$, then $(\lambda(\mathcal{L})-2)(1-\lambda(\mathcal{L}))^{k-2}+1=0$ since $\lambda(\mathcal{L})\geq 2$. We must have that $\lambda(\mathcal{L})>2$, since $f(2)=1>0$ and $f$ is decreasing in $(2,\infty)$. Here $f(\mu):=(\mu-2)(1-\mu)^{k-2}+1$. On the other hand, if all $y_{t}$ with $t\in[k-1]$ are zero, we get that $\mathbf{w}=0$ which is a contradiction. Hence, we must have that $x\prod_{s\in[k-1]\setminus\{j\}}y_{s}=0$ and $y_{j}\neq 0$ for some $j\in[k-1]$, since $x\prod_{s\in[k-1]}y_{s}=0$. These two facts will contradict the fact that

since $k-1$ is even. Thus, this situation can never happen.

If $z_{1}=\cdots=z_{k-1}=z\neq 0$, then $y_{1}=\cdots=y_{k-1}=:y\neq 0$ since $y_{j}=(1-\lambda(\mathcal{L}))z_{j}$. By Definition 2.1, we have $0\leq(\lambda(\mathcal{L})-1)x^{k-1}=-y^{k-1}\leq 0$. Hence $x=y=0$, which is a contradiction. Then, we must have that $z=0$. The equations of the H-eigenvalue $\lambda(\mathcal{L})$ become

If $\lambda(\mathcal{L})>2$, we must have $y_{1}=\cdots=y_{k-1}=:y$, since $(\lambda(\mathcal{L})-2)y_{j}^{k}=-x\prod_{s\in[k-1]}y_{s}$ for all $j\in[k-1]$. Similarly, we must have $x=y=0$ which is a contradiction. Hence, $\lambda(\mathcal{L})=2$. An H-eigenvector would be $y_{1}=1$ and the rest are zero. $\Box$

Power Hypergraphs

Some facts on the H-eigenvalues and H-eigenvectors of the Laplacian tensor of a power hypergraph are investigated in this section.

In this subsection, we show that the largest H-eigenvalue of the Laplacian tensor of an odd-uniform hypercycle (hyperpath) is equal to the maximum degree, i.e., $2$.

If $e$ has only one intersectional vertex $i$, and $x_{s}\neq 0$ for some cored vertex $s\in e$, then $(1-\lambda)x_{s}=x_{i}$.

If $e$ has two intersectional vertices $i$ and $j$, and $x_{s}\neq 0$ for some cored vertex $s\in e$, then $x_{i}x_{j}=(1-\lambda)x_{s}^{2}$.

Proof. For (i), by Definition 2.1 and Lemma 3.1, we have

For (ii), by Definition 2.1 and Lemma 3.1, we have

Thus, $x_{i}x_{j}=(1-\lambda)x_{s}^{2}$. $\Box$

The next corollary is a direct consequence of Lemma 4.1.

If $e$ has only one intersectional vertex $i$, and $x_{s}\neq 0$ for some cored vertex $s\in e$, then $x_{i}x_{s}<0$.

If $e$ has two intersectional vertices $i$ and $j$, and $x_{s}\neq 0$ for some cored vertex $s\in e$, then $x_{i}x_{j}<0$.

Let $k$ be odd and $G=(V,E)$ be a $k$-uniform hypercycle with size being $r\geq 2$. Let $\mathcal{L}$ be its Laplacian tensor. Then $\lambda(\mathcal{L})=2$.

(I). If $x_{s}\neq 0$ for all $s\in[r]$, by Lemma 4.1, we have that $y_{s}y_{s+1}<0$ with $y_{r+1}:=y_{1}$ for all $s\in[r]$. Thus, if $r$ is odd, we get a contradiction by the rule of signs. In the following, we assume that $r$ is even and $\lambda(\mathcal{L})>2$. By Definition 2.1, we have

with the convention that $x_{0}=x_{r}$, $x_{r+1}=x_{1}$, and $y_{0}=y_{r}$, $y_{r+1}=y_{1}$. Thus, we have

Since $y_{s}y_{s+1}<0$ and $k$ is odd, we get a contradiction, since $y_{1}^{k}-y_{2}^{k}+y_{3}^{k}+\cdots+y_{r-1}^{k}-y_{r}^{k}$ should be positive (respectively negative) if we let $y_{1}$ be positive (respectively negative). Consequently, $\lambda(\mathcal{L})=2$.

(II). Suppose that $x_{s}=0$ for some $s\in[r]$. If all $x_{s}=0$ for $s\in[r]$. Then, we are done by Definition 2.1. In the following, we assume that $\lambda(\mathcal{L})>2$. By Lemma 4.1, we have that $y_{s}y_{s+1}<0$ whenever $x_{s}\neq 0$.

Without loss of generality, we assume that $x_{r}=0$, $y_{1}\neq 0$, $x_{1}\neq 0$, $\cdots$, $y_{m}\neq 0$ for some $m\leq r$. Moreover, we can assume that $y_{1}>0$. By Definition 2.1, we have

Since $y_{2}<0$, we have that $x_{1}>0$. Also,

Then, we must have $x_{2}<0$. Inductively, we have $x_{s}y_{s+1}<0$. Hence, $x_{m-1}y_{m}<0$ which implies that $x_{m-1}y_{m-1}>0$. By Definition 2.1, we have

Thus, a contradiction is derived. Consequently, $\lambda(\mathcal{L})=2$. $\Box$

Let $k$ be odd and $G=(V,E)$ be a $k$-uniform hyperpath with length being $r\geq 3$. Let $\mathcal{L}$ be its Laplacian tensor. Then $\lambda(\mathcal{L})=2$.

(I). If both $x_{1}$ and $x_{r}$ are zero, then the proof is same as that for the proof (II) in Proposition 4.1, since we always has a piece of the hyperpath with $y_{t},x_{t+1},\ldots,y_{m}\neq 0$ for some $m\geq t\geq 1$.

(II). If $x_{1}\neq 0$ and $x_{r}=0$, then we can find some $m\geq 1$ such that $x_{1},y_{1},\ldots,y_{m}\neq 0$. We can assume that $y_{1}>0$. By Lemma 4.1, we have $x_{1}<0$. By Definition 2.1, we have

Since $y_{2}<0$ by Lemma 4.1, we have that $x_{2}>0$. Also,

Then, we must have $x_{3}>0$. Inductively, we have $x_{s}y_{s}<0$. Hence, $x_{m}y_{m}<0$ which implies that $x_{m}y_{m-1}>0$. By Definition 2.1, we have

Thus, a contradiction is derived. Consequently, $\lambda(\mathcal{L})=2$.

(III). The proof for the case $x_{1}=0$ and $x_{r}\neq 0$ is similar. Actually, it follows from (II) immediately by renumbering the indices.

(IV). If $x_{s}\neq 0$ for all $s\in[r]$. Similar to (II), we have that $x_{s}y_{s}<0$. Particularly, we have $x_{r-1}y_{r-1}<0$ which implies that $x_{r-1}y_{r-2}>0$. By Definition 2.1, we have

Thus, a contradiction is derived. Consequently, $\lambda(\mathcal{L})=2$.

The other cases can be handled by the above proof as well. $\Box$

By Propositions 5.6, 4.1 and 4.2, we get that [10, Conjecture 3.1] has a negative answer.

2 Even-Uniform Power Hypergraphs

We have a conjecture for even-uniform hypergraphs.

Let $G=(V,E)$ be an usual graph, $k=2r$ be even and $G^{k}=(V^{k},E^{k})$ be the $k$-power hypergraph of $G$. Let $\mathcal{L}^{k}$ and $\mathcal{Q}^{k}$ be the Laplacian and signless Laplacian tensors of $G^{k}$ respectively. Then $\{\lambda(\mathcal{L}^{k})=\lambda(\mathcal{Q}^{k})\}$ is a strictly decreasing sequence.

By [10, Theorem 3.1 and Corollary 5.1], we have the next proposition.

Conjecture 4.1 is true for hyperstars and hypercycles.

Proof. For the case of hyperstars, by [10, Theorem 3.1], we have that $\lambda(\mathcal{L}^{k})$ is the unique root of

Here $d$ is the size of the hyperstar. Let $f_{k}(\mu):=(1-\mu)^{k-1}(\lambda-d)+d$. We have $f_{(}k+1)(d)=d>0$ and

Hence, $\lambda(\mathcal{L}^{k+1})\in(d,\lambda(\mathcal{L}^{k}))$.

The proof for the other case is similar. $\Box$

H-Spectra of Special Power Hypergraphs

We compute out all the H-eigenvalues of some special power hypergraphs in this section.

Let $G=(V,E)$ be a $k$-uniform hyperstar with $k\geq 3$ and the size $d\geq 2$, where $V=[n]$, $E=\{e_{1},\cdots,e_{d}\}$, and $d_{1}=d$ (i.e., the vertex 1 is the heart). Let $\mathcal{L}=\mathcal{D}-\mathcal{A}$ be the Laplacian tensor of $G$. Then it is easy to see that the eigenvalue equations $(\lambda\mathcal{I}-\mathcal{L})\mathbf{x}^{k-1}=0$ are equivalent to the following set of relations:

where $e(j)$ denotes the unique edge containing the vertex $j$ for $j\geq 2$.

The next lemma strengthens Lemma 4.1 for the case of hyperstars.

Let $G,k,d$ and $\mathcal{L}$ be as above. Suppose that $(\lambda,x)$ is an H-eigenpair of $\mathcal{L}$ with $\lambda\neq 1$. Then we have:

If $i,j\geq 2$ and $i,j$ are adjacent (there is an edge containing both $i$ and $j$), then $x_{i}=x_{j}$ when $k$ is odd, and $|x_{i}|=|x_{j}|$ when $k$ is even.

If $i,j\geq 2$ and $x_{i}$, $x_{j}$ are both nonzero, then $x_{i}=x_{j}$ when $k$ is odd, and $|x_{i}|=|x_{j}|$ when $k$ is even.

(ii) Case 1: $k$ is odd. If $j\geq 2$ and $x_{j}\neq 0$, by (3) and the result (i) of this lemma we also have $x_{1}=(1-\lambda)x_{j}$.

Similarly for $i\geq 2$ and $x_{i}\neq 0$, we also have $x_{1}=(1-\lambda)x_{i}$. From this we obtain that $x_{i}=x_{j}$.

Case 2: $k$ is even. If $j\geq 2$ and $x_{j}\neq 0$, by taking the absolute values of the both sides of Eq. (2) and using the result (1) of this lemma we also have $|x_{1}|=|(1-\lambda)x_{j}|$.

Similarly for $i\geq 2$ and $x_{i}\neq 0$, we also have $|x_{1}|=|(1-\lambda)x_{i}|$. From this we obtain that $|x_{i}|=|x_{j}|$. $\Box$

From Lemma 5.1 we can obtain the set of all distinct H-eigenvalues and all corresponding H-eigenvectors of the Laplacian tensor $\mathcal{L}$ of the hyperstar $G$ (except for the eigenvalue 1) in the following Proposition 5.1 (for the case when $k$ is odd) and Proposition 5.2 (for the case when $k$ is even). The set of all eigenvectors corresponding to the eigenvalue 1 will be given in Proposition 5.3.

Let $G=(V,E)$ be a $k$-uniform hyperstar with odd $k\geq 3$ and the size $d\geq 2$, where $V=[n]$, $E=\{e_{1},\cdots,e_{d}\}$, and $d_{1}=d$ (i.e., the vertex 1 is the heart). Let $\mathcal{L}=\mathcal{D}-\mathcal{A}$ be the Laplacian tensor of $G$. Let

$\lambda\neq 1$ is an H-eigenvalue of $\mathcal{L}$ if and only if it is a real root of the polynomial $f_{r}(\lambda)$ for some $r\in\{0,1,\cdots,d\}$.

If $\lambda\neq 1$ is a real root of the polynomial $f_{r}(\lambda)$, then we can construct all the H-eigenvectors of $\mathcal{L}$ corresponding to $\lambda$ (up to a constant multiple) by going through the following procedure:

Step 2: Choose any $r$ edges of $G$, take the $x$-values of all the pendant vertices of these $r$ edges to be 1.

Step 3: Take the $x$-values of all the other vertices of $G$ to be zero.

Proof: (i) Necessity. Let $(\lambda,\mathbf{x})$ is an H-eigenpair of $\mathcal{L}$ with $\lambda\neq 1$.

According to the results of Lemma 5.1, we call an edge $e$ as $x$-nonzero, if the common $x$-value of all the pendant vertices of $e$ is nonzero. Otherwise this edge is called $x$-zero.

Let $r$ be the number of $x$-nonzero edges of $G$. Then we have $0\leq r\leq d$. If $r=0$, then $\mathbf{x}=(1,0,\cdots,0)^{T}$ is an H-eigenvector corresponding to the eigenvalue $d$, which is the unique root of $f_{0}(\lambda)$ other than 1. So in the following, we may assume that $1\leq r\leq d$.

By result (ii) of Lemma 5.1, we may assume that $x_{i}=1$ for all $i\geq 2$ with $x_{i}\neq 0$ (up to a constant multiple). In this case, we also have $x_{1}=1-\lambda$.

Now from (2) we further have $(\lambda-d)x_{1}^{k-1}=-r$. Combining this with $x_{1}=1-\lambda$ we obtain that $(\lambda-d)(1-\lambda)^{k-1}+r=0$, which means that $\lambda$ is a real root of the polynomial $f_{r}(\lambda)$.

Sufficiency part of (i) follows directly from the constructive procedure of result (ii).

(ii) It is not difficult to verify that any vector $x$ obtained after going through the steps 1-3 will satisfy the (2) and (3), so it is an H-eigenvector corresponding to the H-eigenvalue $\lambda$. $\Box$

Now we consider the case when $k$ is even.

Let $G=(V,E)$ be a $k$-uniform hyperstar with even $k\geq 4$ and the size $d\geq 2$, where $V=[n]$, $E=\{e_{1},\cdots,e_{d}\}$, and $d_{1}=d$. Let $\mathcal{L}=\mathcal{D}-\mathcal{A}$ be the Laplacian tensor of $G$. Then we have:

$\lambda\neq 1$ is an H-eigenvalue of $\mathcal{L}$ if and only if it is a real root of the polynomial $f_{r}(\lambda)$ for some $r\in\{0,1,\cdots,d\}$.

If $\lambda\neq 1$ is a real root of the polynomial $f_{r}(\lambda)$, then we can construct all the H-eigenvectors of $\mathcal{L}$ corresponding to $\lambda$ (up to a constant multiple) by going through the following procedure:

Step 2: Choose any $r$ edges of $G$, take the $x$-values of all the pendant vertices of these $r$ edges to be $\pm 1$, where the number of $-1$ value in each edge is even.

Step 3: Take the $x$-values of all the other vertices of $G$ to be zero.

Proof: (i) Necessity. Let $(\lambda,x)$ be an H-eigenpair of $\mathcal{L}$ with $\lambda\neq 1$.

Let $r$ be the number of $x$-nonzero edges of $G$. Then we have $0\leq r\leq d$.

By result (ii) of Lemma 5.1, we may assume that $x_{i}=\pm 1$ for all $i\geq 2$ with $x_{i}\neq 0$ (up to a constant multiple). In this case, we also have $x_{1}=\pm(1-\lambda)$ by (3). We now consider the following two cases:

Case 1: $x_{1}=(1-\lambda)$ . Then from (3) we have $\prod_{s\in e(j)\backslash\{1\}}x_{s}=1$ for $j\geq 2$ and $x_{j}\neq 0$. Thus from (2) we further have $(\lambda-d)x_{1}^{k-1}=-r$. Combining this with $x_{1}=1-\lambda$ we obtain that $(\lambda-d)(1-\lambda)^{k-1}+r=0$, which means that $\lambda$ is a real root of the polynomial $f_{r}(\lambda)$.

Case 2: $x_{1}=-(1-\lambda)$ . Then from (3) we have $\prod_{s\in e(j)\backslash\{1\}}x_{s}=-1$ for $j\geq 2$ and $x_{j}\neq 0$. Thus from (2) we further have $(\lambda-d)x_{1}^{k-1}=r$. Combining this with $x_{1}=-(1-\lambda)$ and the hypothesis that $k$ is even, we also obtain that $(\lambda-d)(1-\lambda)^{k-1}+r=0$, which means that $\lambda$ is a real root of the polynomial $f_{r}(\lambda)$.

Notice that the eigenvectors $x$ constructed in Case 1 and Case 2 only differ by a multiple $-1$, so we only need to consider Case 1.

Sufficiency part of (i) follows directly from the constructive procedure of result (ii).

(ii) It is not difficult to verify that any vector $x$ obtained after going through the steps 1-3 will satisfy the (2) and (3), so it is an H-eigenvector corresponding to the H-eigenvalue $\lambda$. $\Box$

Now we construct all the eigenvectors of $\mathcal{\mathcal{L}}$ corresponding to the eigenvalue 1.

Let $G=(V,E)$ be a $k$-uniform hyperstar with $k\geq 3$ and the size $d\geq 2$, where $V=[n]$, $E=\{e_{1},\cdots,e_{d}\}$, and $d_{1}=d$. Let $\mathcal{L}=\mathcal{D}-\mathcal{A}$ be the Laplacian tensor of $G$. Then a nonzero vector $x$ is an eigenvector corresponding to the eigenvalue 1 if and only if $x_{1}=0$ and the $x$-values of all the pendant vertices of $G$ satisfy the following relation:

Necessity. Suppose that $\mathbf{x}$ is an eigenvector corresponding to the eigenvalue 1. If $x_{1}\neq 0$, then from (5) we see that each edge of $G$ contains at least two pendant vertices whose $x$-values are zero. From this and the (2), we would have $d=1$, a contradiction. So we have that $x_{1}=0$.

Now $x_{1}=0$ means that (2) becomes (4). This proves the necessity part.

Sufficiency. It is easy to verify that if $x_{1}=0$ and the $x$-values of all the pendant vertices of $G$ satisfy the relation (4), then $x$ satisfies (2) and (3) for $\lambda=1$. Thus $x$ is an eigenvector corresponding to the eigenvalue 1. $\Box$

2 Hyperpaths

In this subsection, we consider a hyperpath of length being $3$ when $k$ is odd.

The next lemma follows from [14, Theorem 3].

Let $k$ be odd and $G=(V,E)$ be a $k$-uniform hyperpath with length being $3$. Let $\mathcal{L}$ be its Laplacian tensor. Then $\lambda\neq 1$ is an H-eigenvalue of $\mathcal{L}$ if and only if one of the following four cases happens:

$\lambda$ is the unique root of the equation $(\lambda-2)(1-\lambda)^{k-1}+1=0$, which is in $(0,1)$,

$\lambda$ is the unique root of the equation $(\lambda-2)^{2}(1-\lambda)^{k-2}-1=0$, which is in $(0,1)$, and

$\lambda$ is a real root of the equation $(\lambda-2)^{2}(1-\lambda)^{k-1}+2\lambda-3=0$ in $(0,2)$.

Let $x_{k}=\alpha$ and $x_{2k-1}=\beta$. By Lemmas 3.1 and 4.1, we have $x_{1}=\cdots=x_{k-1}=\frac{1}{1-\lambda}\alpha$ if there are nonzero; $x_{k+1}=\cdots=x_{2k-2}=\pm\sqrt{\frac{\alpha\beta}{1-\lambda}}$ if there are nonzero; and $x_{2k}=\cdots=x_{3k-2}=\frac{1}{1-\lambda}\beta$ if there are nonzero.