Regular Uniform Hypergraphs, $s$-Cycles, $s$-Paths and Their largest Laplacian H-Eigenvalues

Introduction

Let $k\geq 2$ and $n\geq k$. A $k$-uniform hypergraph $G=(V,E)$ has 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$. If $k=2$, we have an ordinary graph.

The largest Laplacian eigenvalue of a graph plays an important role in spectral graph theory . A natural definition for the Laplacian and signless Laplacian tensors of a $k$-uniform hypergraph $G$, where $k\geq 3$, was introduced in . It was shown there that the largest Laplacian H-eigenvalue of $G$ is always less than or equal to the largest signless Laplacian H-eigenvalue of $G$, while the latter is always less than or equal to $2\Delta$, where $\Delta$ is the largest degree of $G$. In , the odd-bipartite hypergraph was introduced. In , it was proved that the largest Laplacian H-eigenvalue of a connected $k$-uniform hypergraph $G$ is equal to its largest signless Laplacian H-eigenvalue if and only if $G$ is odd-bipartite. This result extended the classical result in spectral graph theory .

In this paper, we show that the largest signless Laplacian H-eigenvalue of a connected $k$-uniform hypergraph $G$, where $k\geq 3$, reaches its upper bound $2\Delta$, if and only if $G$ is regular. Thus, the largest Laplacian H-eigenvalue of $G$, reaches the same upper bound, if and only if $G$ is regular and odd-bipartite.

We then turn our attention to $s$-paths and $s$-cycles.

Researchers in hypergraph theory have studied loose cycles, loose paths, tight cycles and tight paths extensively .

Let $G=(V,E)$ be a $k$-uniform hypergraph. Suppose $1\leq s\leq k-1$. According to , if $V=\{i:i\in[s+m(k-s)]\}$ such that $\{1+j(k-s),\cdots,s+(j+1)(k-s)\}$ is an edge of $G$ for $j=0,\cdots,m-1$, then $G$ is called an $s$-path. In , $G$ is called a loose path if $s=1$, and a tight path if $s=k-1$. In , $G$ is also called a loose path for $2\leq s\leq{k\over 2}$ and a tight path for ${k\over 2}<s\leq k-2$. To avoid confusion, in these two cases, as in , we call $G$ a generalized loose path and a generalized tight path respectively. According to , if $V=\{i:i\in[m(k-s)]\}$ such that $\{1+j(k-s),\cdots,s+(j+1)(k-s)\}$ is an edge of $G$ for $j=0,\cdots,m-1$, where vertices $m(k-s)+j\equiv j$ for any $j$, then $G$ is called an $s$-cycle. According to , if $s=1$, $G$ is called a loose cycle, if $s=k-1$, $G$ is called a tight cycle. We call $G$ a generalized loose cycle for $2\leq s\leq{k\over 2}$, and a generalized tight cycle for ${k\over 2}<s\leq k-2$. For an $s$-cycle, in this paper, we assume that $n\geq 2k-s$. In this way, each pair of consecutive edges in the $s$-cycle will have exactly $s$ common vertices. In the next section, we will discuss this in details.

We show in this paper that an $s$-cycle $G$, as a $k$-uniform hypergraph, where $1\leq s\leq k-1$, is regular if and only if $k$ is a multiple of $k-s$.

The Laplacian H-eigenvalues of loose paths and loose cycles were studied in . In , power hypergraphs and cored hypergraphs were introduced. Loose paths and loose cycles are power hypergraphs. Power hypergraphs are cored hypergraphs. Even-uniform cored hypergraphs are odd-bipartite. As cycles are symmetric, their largest signless Laplacian H-eigenvalues can be identified directly. Thus, the largest Laplacian H-eigenvalues of odd-bipartite cycles can be identified directly. In , the largest Laplacian H-eigenvalue of an even-uniform loose cycle was identified directly.

According to , the largest Laplacian H-eigenvalue of $k$-uniform hypergraph is always greater than or equal to the largest degree of that $k$-uniform hypergraph. By , when $k$ is even, equality cannot hold, but when $k$ is odd, equality may hold in certain cases. It was proved in that equality holds for odd-uniform loose paths and loose cycles.

It was observed in that if $2\leq s<{k\over 2}$, then an $s$-path or an $s$-cycle is a cored hypergraph, but not a power hypergraph in general.

These results raised several questions. First, if $k$ is even and ${k\over 2}\leq s\leq k-1$, are some $s$-paths and $s$-cycles still odd-bipartite, though they are not cored hypergraphs? Second, can we identify the largest Laplacian H-eigenvalues of even-uniform odd-bipartite $s$-cycles directly? Third, when $k$ is odd and $2\leq s\leq k-1$, are the largest H-eigenvalues of $s$-paths and $s$-cycles equal to the corresponding largest degrees? We will study these questions in this paper.

We give some basic definitions in the next section.

In Section 3, we prove the result about regular uniform hypergraphs mentioned before, and identify regular $s$-cycles.

In Section 4, we show that if $k$ is even, all the $s$-paths and all the non-regular $s$-cycles are odd-bipartite. We prove that a regular $s$-cycle $G$ with $k=q(k-s)$ is odd-bipartite if and only if $m$ is a multiple of $2^{t_{0}}$, where $m$ is the number of edges in $G$, and $q=2^{t_{0}}(2l_{0}+1)$ for some integers $t_{0}$ and $l_{0}$.

In , several classes of hypergraphs were shown to be odd-bipartite. But only in this paper, some regular $s$-cycles are shown to be not odd-bipartite. To show that a hypergraph is odd-bipartite, one only needs to give an adequate odd-partition for the vertex set of that hypergraph. Such an odd-partition is not unique in general. To show that a hypergraph is not odd-bipartite, one needs to prove that there is no such an odd-partition for the vertex set of that hypergraph. Hence, in general, it is not a trivial task to show that a hypergraph is not odd-bipartite.

In Section 5, we identify the largest Laplacian H-eigenvalues of even-uniform $s$-cycles directly when $2\leq s\leq k-1$. These include all the even-uniform non-regular $s$-cycles, and those odd-bipartite regular $s$-cycles.

We introduce supervertices for hypergraphs in Section 6, and show there that the components of an H-eigenvector of an odd-uniform hypergraph are equal if such components corresponds vertices in the same supervertex, and the corresponding Laplacian H-eigenvalue is not equal to the degree of the supervertex. Using this property, in Section 7, we show that the largest H-eigenvalue of an odd-uniform generalized loose $s$-cycle is equal to $2$, the maximum degree of that $s$-cycle.

In Section 8, we show that the largest Laplacian H-eigenvalue of a $k$-uniform tight $s$-cycle is at least $k+1$, if the number of vertices is even and $k=4l+3$ for some nonnegative integer $l$. Note that in this case $\Delta=k$. We show that equality holds here if $k=3,s=2$ and $n=4$. When $k=3,s=2$, and $n\geq 5$, we show that the largest Laplacian H-eigenvalue is no more than $4.5$.

Some final remarks are made in Section 9.

Preliminaries

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.

Consider a $k$-uniform hypergraph $G=(V,E)$ with vertex set $V$, which is labeled as $[n]=\{1,\ldots,n\}$, and edge set $E$. 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}$. If two vertices $i$ and $j$ are in the same edge $e$, then we denote $i\sim j$. 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 vertices of $G$ is connected. 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 of degree $d={n-1\choose k-1}$.

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 we have $\lambda(\mathcal{L})\leq\lambda(\mathcal{Q})\leq 2\Delta$, where $\Delta$ is the maximum degree of $G$. For ${\cal T}={\cal L}$, the polynomial system $\left(\lambda{\cal I}-{\cal T}\right)\mathbf{x}^{k-1}=0$ in Definition 2.1 has the form

For ${\cal T}={\cal Q}$, the polynomial system $\left(\lambda{\cal I}-{\cal T}\right)\mathbf{x}^{k-1}=0$ in Definition 2.1 has the form

In the following, we define 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 called a cored hypergraph. A vertex with degree one is called a core vertex, and a vertex with degree larger than one is called an intersection vertex.

The notion of odd-bipartite even-uniform hypergraphs was introduced in .

Let $G=(V,E)$ be a $k$-uniform hypergraph. Then $G$ is called odd-bipartite if $k$ is even and either it is trivial (i.e., $E=\emptyset$) or there is a 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.

In the introduction, we claim that $n$, the number of vertices in an $s$-cycle needs to satisfy the condition $n\geq 2k-s$ such that each pair of consecutive edges has exactly $s$ common vertices. We now discuss this in details below.

Let $G=(V,E)$ be a k-uniform $s$-cycle with $n$ vertices and $m$ edges, where $n=m(k-s)$ and $1\leq s\leq k-1$. Then each pair of consecutive edges of G contains exactly $s$ common vertices if and only if $n\geq 2k-s$.

Proof. By the definition, we may assume that $V=[n]$, and may agree that $i=n+i$ when $i$ and $n+i$ are both viewed as vertices of $G$. Also, we have $E=\{e_{0},e_{1},\cdots,e_{m-1}\}$, where

Necessity. If each pair of consecutive edges of G contains exactly $s$ common vertices, then $|e_{0}\cap e_{1}|=s$. On the other hand, we have $|e_{0}\cup e_{1}|+|e_{0}\cap e_{1}|=|e_{0}|+|e_{1}|$. So we have

Sufficiency. Now suppose that $n\geq 2k-s$. Then it is easy to verify that

Since $n\geq 2k-s$ implying $(m-1)(k-s)\geq k$, we can also verify that

Regular Uniform Hypergraphs and Regular s𝑠s-Cycles

We now establish the following theorem for a connected $k$-uniform hypergraph $G$.

Suppose that $G=(V,E)$ is a connected $k$-uniform hypergraph with $k\geq 2$ and maximum degree $\Delta$. Then $\lambda({\mathcal{Q}})=2\Delta$ if and only if $G$ is regular. Furthermore, $\lambda({\mathcal{L}})=2\Delta$ if and only if $G$ is regular and odd-bipartite.

where $d_{i}$ is the degree of vertex $i$. To make this equality hold, we must have $d_{i}=\Delta$ and $x_{j}=x_{i}$ as long as $j\sim i$. Applying the same augment for all such $j$ with $j\sim i$, we have $d_{j}=\Delta$ and $x_{l}=x_{j}=x_{i}$ as long as $l\sim j$. As $G$ is connected, we see that $d_{j}=\Delta$ for all $j\in V$. Thus $G$ is regular.

The last conclusion of this theorem follows from the above conclusion and [9, Theorem 5.1]. $\Box$

Clearly, an $s$-path cannot be regular. We now consider regular $s$-cycles.

Let $G=(V,E)$ be a $k$-uniform $s$-cycle, with $1\leq s\leq k-1$, $k\geq 3$, $V=\{i:i\in[m(k-s)]\}$, such that $\{1+j(k-s),\cdots,s+(j+1)(k-s)\}$ is an edge of $G$ for $j=0,\cdots,m-1$, where vertices $m(k-s)+j\equiv j$ for any $j$. Then $G$ is regular if and only if $k=q(k-s)$ for some positive integer $q$. In this case, we have $d_{1}=\cdots=d_{n}=q$, where $n=m(k-s)=|V|$.

Proof. If $k=q(k-s)$, then we see that $d_{1}=\cdots=d_{n}=q$. Hence $G$ is regular in this case. On the other case, suppose $k=q(k-s)+r$, where $1\leq r<k-s$. Then we see that $d_{1}=q+1$ and $d_{k-s}=q$. Thus, $G$ cannot be regular in this case.

The conclusions of this proposition follow now. $\Box$

Since $1\leq s\leq k-1$, we see that $2\leq q\leq k$. For a tight cycle, $s=k-1$, we see that $G$ is also regular with $q=k$ in this case. Thus, we have the following corollary.

Odd-Bipartite s𝑠s-Paths and s𝑠s-Cycles

We assume that $k$ is even in this section, as odd-bipartite hypergraphs are only for even $k$.

Our first proposition in this section shows that when $k$ is even, all the $s$-paths are odd-bipartite.

Assume that $k\geq 4$ is even. Let $G=(V,E)$ be a $k$-uniform $s$-path, where $1\leq s\leq k-1$. Then $G$ is odd-bipartite.

Proof. According the discussion at the beginning of this paper, we may assume that $V=\{i:i\in[s+m(k-s)]\}$ such that $\{1+j(k-s),\cdots,s+(j+1)(k-s)\}$ is an edge of $G$ for $j=0,\cdots,m-1$. Let $V_{1}=\{k,2k,\cdots,\}$ and $V_{2}=V\setminus V_{1}$. Then we see that $G$ is odd-bipartite as each edge has exactly one vertex in $V_{1}$. $\Box$

2 Odd-bipartite Non-Regular s𝑠s-Cycles

Our second proposition in this section shows that when $k$ is even, all the non-regular $s$-cycles are odd-bipartite.

Assume that $k\geq 4$ is even. Let $G=(V,E)$ be a $k$-uniform non-regular $s$-cycle, where $1\leq s\leq k-1$. Then $G$ is odd-bipartite.

Proof. When $s=1$, $G$ is a loose cycle, thus a power hypergraph . When $1<s<{k\over 2}$, $G$ has at least one core vertex, thus is a cored hypergraph . In both cases, $G$ is odd-bipartite as long as $k$ is even, as observed in .

Now, by Proposition 3.1, the remaining case, after excluding regular $s$-cycles, are that ${k\over 2}<s<k-2$, $k=q(k-s)+r$, where $1\leq r\leq k-s-1$. We may assume that $V=\{i:i\in[m(k-s)]\}$, and note that vertices $j+m(k-s)\equiv j$ for all $j$. If $q$ is odd, let $V_{1}=\{i(k-s):i\in[m]\}$ and $V_{2}=V\setminus V_{1}$. Then each edge has exactly $q$ vertices in $V_{1}$. If $q$ is even, let $V_{1}=\{1+(i-1)(k-s):i\in[m]\}$ and $V_{2}=V\setminus V_{1}$. Then each edge has exactly $q+1$ vertices in $V_{1}$. In both cases, each edge has odd number of vertices in $V_{1}$. Thus, $G$ is odd-bipartite as long as $k$ is even. $\Box$

3 Odd-bipartite Regular s𝑠s-Cycles

We now give a sufficient and necessary condition for a regular $s$-cycle to be odd-bipartite.

Let $G=(V,E)$ be a k-uniform $s$-cycle with $n$ vertices and $m$ edges, where $n=m(k-s)$, $k$ is even and $1\leq s\leq k-1$. Assume that there is an integer $q$ such that $k=q(k-s)$ (Thus $G$ is regular by Proposition 3.1). Write $q=2^{t_{0}}(2l_{0}+1)$ for some nonnegative integers $t_{0}$ and $l_{0}$. Then $G$ is odd-bipartite if and only if $m$ is a multiple of $2^{t_{0}}$.

Proof. We assume that $V=Z_{n}$ (the set of integers modulo n). Namely, we agree that $i=n+i$, when $i$ and $n+i$ are both viewed as vertices of $G$.

Also, the edges $e_{0},e_{1},\cdots,e_{m-1}$ of $G$ are as follows:

where each edge consists of k cyclicly consecutive vertices of $G$.

Sufficiency. Suppose that $m=2^{t_{0}}p_{0}$. Let $q_{0}=2^{t_{0}}(k-s)$. Then we have $n=m(k-s)=p_{0}q_{0}$. Let

be the set of all the multiples of $q_{0}$ in the set $Z_{n}$.

Since $k=q_{0}(2l_{0}+1)$ and $n=p_{0}q_{0}$ are both multiples of $q_{0}$, we see that each set of k cyclicly consecutive elements in $Z_{n}$ contains exactly $\frac{k}{q_{0}}=2l_{0}+1$ elements which are multiples of $q_{0}$. Thus each edge of $G$ contains exactly $2l_{0}+1$ vertices in $V_{1}$. Hence $G$ is odd-bipartite.

Necessity. We write $a\sim b$ if the two integers $a$ and $b$ have the same parity. Let

Then we have $|X_{j}|=k-s$ and $V=Z_{n}=\cup_{j=0}^{m-1}X_{j}$. Also we agree that $X_{m+j}=X_{j}$ (as subsets of $Z_{n}$).

Now suppose that $G$ is odd-bipartite with the bipartition $(V_{1},V_{2})$. Let

Then by the definition of odd-bipartition, all $b_{0},b_{1},\cdots,b_{m-1}$ are odd.

On the other hand, since $X_{m+i}=X_{i}$ we also have

Let $g=gcd(m,q)$ be the greatest common divisor of $m$ and $q$. Then $g=cm+dq$ for some integers $c$ and $d$. So by (7) and (8) we have

Now let $q^{\prime}=q/g$. Then $q=gq^{\prime}$, so by (9) we have

Since $b_{0}$ is odd, $q^{\prime}$ is also odd, which implies that $g$ is a multiple of $2^{t_{0}}$. Thus $m$ is also a multiple of $2^{t_{0}}$. $\Box$

Figure 1 indicates an odd-bipartite regular $3$-cycle with $k=2(k-s)=6$ and $m=4$. We see that $G$ is odd-bipartite with $V_{1}=\{6,12\}$ and $V_{2}=V\setminus V_{1}$.

The smallest non-odd-bipartite even-uniform regular $s$-cycle may be as follows: $k=4,s=2$ and $m=3$ (thus $n=6$. Using Matlab, we find that the Laplacian H-eigenvalues of this $2$-cycle are $0,1,2$ and $3$ only. Thus, $\lambda({\cal L})=3<2\Delta=4$ in this example. This confirms Theorem 4.1.

In Theorem 4.1, if $k$ is even and $q$ is odd, then $G$ is odd-bipartite.

If $s=k-1$, then $G$ is a tight cycle. We have the following corollary.

Let $G=(V,E)$ be a $k$-uniform tight cycle, i.e., $s=k-1$. Then $G$ is regular. Assume that $k$ is even. We may write $k=2^{t_{0}}(2l_{0}+1)$ for two nonnegative integers $t_{0}$ and $l_{0}$. Then $G$ is odd-bipartite if and only if $m=n$ is a multiple of $2^{t_{0}}$.

The Largest Laplacian H-eigenvalue of Odd-Bipartite s𝑠s-Cycles

In this section, we identify the largest signless Laplacian H-eigenvalues of $s$-cycles in all possible cases. When these $s$-cycles are odd-bipartite, these values are also their largest Laplacian H-eigenvalues.

This is the case that $1\leq s<{k\over 2}$. Suppose $G=(V,E)$ is such an $s$-cycle. Then for each edge, there are $k-2s$ core vertices, and $2s$ intersection vertices.

Now we take ${\bf x}\in\Re^{n}$ be a positive vector with $x_{i}=\alpha>0$ if $i$ is a core vertex, and $x_{j}=1$ if $j$ is an intersection vertex. Suppose that $\mathbf{x}$ is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $\mu=\lambda(\mathcal{Q})$. Note that the degree of a core vertex is $1$ and the degree of an intersection vertex is $2$. By (3), we would have

Since $f(0)=-1<0$ and $f(1)=2>0$, (10) has a root $\alpha_{*}\in(0,1)$. Let $\mu_{*}=2+2\alpha_{*}^{k-2s}$. Then $\lambda(\mathcal{Q})=\mu_{*}$. By , since $G$ is a cored hypergraph, we have $\lambda(\mathcal{L})=\mu_{*}$ if $k$ is even.

We conclude this discussion as the following theorem.

Suppose that $G=(V,E)$ is an $s$-cycle with $k\geq 3$ and $1\leq s<{k\over 2}$. Then $\lambda(\mathcal{Q})=2+2\alpha_{*}^{k-2s}$, where $\alpha_{*}$ is the unique root of (10) in $(0,1)$. When $k$ is even, we have $\lambda(\mathcal{L})=2+2\alpha_{*}^{k-2s}$ too.

Note that in this case $\Delta=2$ and we have $\Delta=2<\lambda(\mathcal{Q})<2\Delta=4$. This confirms Theorem 3.1 and [17, Corollary 6.2].

2 Regular s𝑠s-Cycles

By Proposition 3.1 and Theorem 4.1, we have the following proposition.

Suppose that $G=(V,E)$ is an $s$-cycle with $k=q(k-s)\geq 3$. Then $G$ is a regular hypergraph and $\lambda(\mathcal{Q})=2q$. Assume further that $k$ is even. If either $q$ is odd or $q=2^{t_{0}}(2l_{0}+1)$ for a positive integer $t_{0}$ and a nonnegative integer $l_{0}$, and $m$ is a multiple of $2^{t_{0}}$, then we have $\lambda(\mathcal{L})=2q$ too.

It will be a further research topic to find the value of $\lambda(\mathcal{L})$ for a non-odd-bipartite regular $s$-cycle.

3 Non-Regular Generalized Tight s𝑠s-Cycles

In this subsection, we consider a generalized tight $s$-cycle $G=(V,E)$, which is not a regular $s$-cycle. We may assume that ${k\over 2}<s<k-1$ and $k=q(k-s)+r$, where $1\leq r<k-s$. Then for each edge, there are $(q+1)r$ vertices with degree $q+1$, and $k-(q+1)r$ vertices with degree $q$.

Now we take ${\bf x}\in\Re^{n}$ be a positive vector with $x_{i}=\alpha>0$ if $i$ is a vertex with degree $q$, and $x_{j}=1$ if $j$ is a vertex with degree $q+1$. Suppose that $\mathbf{x}$ is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $\mu=\lambda(\mathcal{Q})$. By (3), we should have

Since $f(0)=-q<0$ and $f(1)=2>0$, (11) has a root $\alpha_{*}\in(0,1)$. Let $\mu_{*}=q+1+(q+1)\alpha_{*}^{k-(q+1)r}$. Then $\lambda(\mathcal{Q})=\mu_{*}$. If $k$ is even, then $G$ is odd-bipartite. By , we have $\lambda(\mathcal{L})=\mu_{*}$ in this case.

We conclude this discussion as the following theorem.

Suppose that $G=(V,E)$ is an $s$-cycle with $k\geq 3$ and ${k\over 2}<s<k-1$, $k=q(k-s)+r$, with $1\leq r<k-s$. Then $\lambda(\mathcal{Q})=q+1+(q+1)\alpha_{*}^{k-(q+1)r}$, where $\alpha_{*}$ is the unique root of (11) in $(0,1)$. When $k$ is even, we have $\lambda(\mathcal{L})=q+1+(q+1)\alpha_{*}^{k-(q+1)r}$ too.

In this case $\Delta=q+1$ and we have $\Delta=q+1<\lambda(\mathcal{Q})<2\Delta=2(q+1)$. This also confirms Theorem 3.1 and [17, Corollary 6.2].

Note that all $s$-cycles are covered by the discussion in these three subsections.

Supervertices

We now define supervertices for a $k$-uniform hypergraph.

Let $G=(V,E)$ be a $k$-uniform hypergraph. Let $i\in V$. The vertex set

is called a supervertex of $G$. Clearly, any vertex in the same supervertex has the same degree. We call this degree the degree of that supervertex. In particular, if a supervertex contains a core vertex, then all vertices in that supervertex are core vertices. We call such a supervertex a core supervertex. Otherwise, we call it an intersection supervertex.

For example, in Figure 1, there are four intersection supervertices $\{1,2,3\},\{4,5,6\},\{7,8,9\}$, $\{10,11,12\}$. For a loose cycle or a generalized loose $s$-cycle with $1\leq s<{k\over 2}$, there are $m$ core supervertices and $m$ intersection supervertices, where $m$ is the number of edges in that $s$-cycle. Each core supervertex has cardinality $k-2s$. Each intersection supervertex has degree $2$ and cardinality $s$.

Suppose that $G=(V,E)$ is a $k$-uniform hypergraph with $k\geq 3$. Let $U$ be a supervertex of $G$, with degree $d$ and cardinality $|U|\geq 2$. Suppose that $\lambda$ is a Laplacian H-eigenvalue of $G$, $\lambda\not=d$. Let $\bf x$ be a Laplacian H-eigenvector of $G$, corresponding to $\lambda$. Suppose $i,j\in U$. Then $|x_{i}|=|x_{j}|$. If $k$ is odd, then $x_{i}=x_{j}$.

As $\lambda\not=d$, we have $x_{i}^{k}=x_{j}^{k}$. The conclusions follow from this equality. $\Box$

Note that Lemma 3.1 of is a special case of this theorem.

Odd-Uniform Generalized Loose s𝑠s-Cycles

In this section, assuming that $k$ is odd, using Theorem 6.1, we show that the largest Laplacian H-eigenvalue of an odd-uniform generalized loose $s$-cycle is equal to $2$, the maximum degree of that $s$-cycle. This result extends the result on odd-uniform loose cycles in Subsection 4.1 of . Since $k$ is odd, the case that $k=2s$ is not included. Thus, we have $1\leq s<{k\over 2}$. The $s$-cycle has always core vertices.

Suppose that $G=(V,E)$ is an $s$-cycle with $1\leq s<{k\over 2}$ and $k$ is odd. Then $\lambda(\mathcal{L})=\Delta=2$. If $s$ is even, then the only Laplacian H-eigenvalue $\lambda$ of $G$, satisfying $\lambda>1$, is $2$.

Proof. Suppose that $G$ has $m$ edges. Then $G$ has $m$ core supervertices $V_{i},i\in[m]$ and $m$ intersection supervertices $U_{i},i\in[m]$, displayed as $U_{1},V_{1},U_{2},V_{2},\cdots,U_{m},V_{m},U_{m+1}\equiv U_{1}$, such that the edges of $G$ are $e_{i}=U_{i}\cup V_{i}\cup U_{i+1},i\in[m]$. For $i\in[m],|U_{i}|=s,|V_{i}|=k-2s$. Furthermore, assume that the vertices of $G$ are $j\in[n]$, where $n=m(k-s)$. Then $U_{i}=\{(i-1)(k-s)+j:j\in[s]\}$, $V_{i}=\{(i-1)(k-s)+s+j:j\in[k-2s]$ }, for $i\in[m]$.

Suppose that $\lambda>1$, $\lambda\not=2$ is a Laplacian H-eigenvalue of $G$. Let $\bf z$ be an Laplacian H-eigenvector corresponding to $\lambda$. By Theorem 6.1, we may assume that for $i\in m$, $y_{i}=z_{j}$ for $j\in U_{i}$, $x_{i}=z_{j}$ for $j\in V_{i}$. Let $y_{m+1}\equiv y_{1}$, $x_{0}\equiv x_{m}$, $y_{0}\equiv y_{m}$.

If $s$ is even, by (12), we must have $x_{i}=0$ for all $i\in[m]$, otherwise we would have $\lambda x_{i}^{k-1}>x_{i}^{k-1}>x_{i}^{k-1}-x_{i}^{k-2s-1}y_{i}^{s}y_{i+1}^{s}$ for some $i$, contradicting (12). This implies that $y_{i}\not=0$ for at least one $i$. By (13), this implies that $\lambda=2$, a contradiction. This proves that when $s$ is even, $\lambda>1$ implies $\lambda=2$. The conclusion for the case that $s$ is even is proved.

From now we assume that $s$ is odd and $\lambda>2$. Then by (12), we see that $x_{i}\not=0$ implies that $y_{i}y_{i+1}<0$.

(i). First assume that $x_{i}\not=0$ for all $i\in[m]$. By (12), we have $y_{i}y_{i+1}<0$ for $i\in[m]$. Thus, $m$ must be even, otherwise we get a contradiction by the rule of alternating signs of $y_{1},\cdots,y_{m}$. Assume that $m$ is even. By (13), we have

Since $y_{i}y_{i+1}<0$ for $i\in[m]$, we get a contradiction, as $y_{1}^{k}-y_{2}^{k}+y_{3}^{k}-\cdots+y_{m-1}^{k}-y_{m}^{k}$ should have the same sign as $y_{1}$, which is nonzero. The conclusion follows now.

(ii). We now assume $x_{i}=0$ for all $i\in[m]$. This implies that $y_{i}\not=0$ for at least one $i$. By (13), this implies that $\lambda=2$, a contradiction.

(iii). Finally, we assume that $x_{i}=0$ for some $i\in[m]$ and $x_{i}\not=0$ for other $i\in[m]$. Without loss of generality, we may assume that $x_{1}>0$ and $x_{m}=0$. By (12), we have $y_{1}y_{2}<0$. By taking $i=1$ in (14), we have

Now we use induction to show that $x_{i}y_{i}>0$ for $i=1,\cdots,m$. The case $i=1$ follows from $x_{1}>0$ and $y_{1}>0$. We assume $i\geq 2$ and $x_{i-1}y_{i-1}>0$. Then $y_{i}\neq 0$ since $x_{i-1}\neq 0$ implying $y_{i-1}y_{i}<0$. From (14) we have (since $k$ and $s$ are both odd):

which implies $x_{i}\neq 0$ and $x_{i}y_{i+1}<0$. But $x_{i}\neq 0$ also implies $y_{i}y_{i+1}<0$, so we obtain $x_{i}y_{i}>0$ and thus complete the inductive proof. Taking $i=m$ in $x_{i}y_{i}>0$, we obtain $x_{m}\neq 0$, a contradiction.

Thus, when $s$ is odd, we cannot have $\lambda>2$. This implies that $\lambda(\mathcal{L})=\Delta=2$. $\Box$

Odd-Uniform Tight s𝑠s-Cycles

In this section, we assume that $k$ is odd and $s=k-1$. Then we have tight $s$-cycles. We will see that the results on the largest Laplacian H-eigenvalues here are very different from those in the last section.

Suppose that $G=(V,E)$ is a tight $s$-cycle with $s=k-1$ and $k=4l+3$ for a nonnegative integer $l$. Then $\Delta=k$. When $n$, the number of vertices, is even, we have $\lambda(\mathcal{L})\geq\Delta+1=k+1$.

Proof. Let ${\bf x}\in\Re^{n}$ be defined by $x_{2i-1}=1$ and $x_{2i}=-1$ for $i\in\left[{n\over 2}\right]$. Also, we assume that $x_{n+i}\equiv x_{i}$ for any $i$. From this we see that the sum of any $k-1$ consecutive components of $\bf x$ is zero, and the product of any $k-1=4l+2$ consecutive components of $\bf x$ is $(-1)^{2l+1}=-1$. Thus we have

Now multiplying the both sides of (2) by $x_{i}$, we obtain

This shows that $\lambda=k+1$ and $\bf x$ satisfy this system, i.e., $\lambda=k+1$ is an H-eigenvalue of $\cal L$. As $\Delta=k$, the conclusion follows. $\Box$

This is the second example that $\lambda(\mathcal{L})>\Delta$ when $k$ is odd. The first example for this is the $3$-uniform complete hypergraph, given in . By using supervertices, we may generalize this result to $k$-uniform regular $s$-cycles, with $k=q(k-s)$, $q=4l+3$ for some $l$, where $k-s$ and $m$ are even.

We do not know what kind of result can be established for $k=4l+1$. But for $k=3$, we can get the exact value of $\lambda(\mathcal{L})$ when $n=4$, and an upper bound of $\lambda(\mathcal{L})$ for all $n$.

Suppose that $G=(V,E)$ is a tight $s$-cycle with $s=2$ and $k=3$. Then $\Delta=3$. When $n=4$, we have $\lambda(\mathcal{L})=4$. When $n\geq 5$, we have $\lambda(\mathcal{L})\leq\Delta+1.5=4.5$.

Proof. When $k=3,s=2$ and $n=4$, (2) has the form:

Since $\sum_{i=1}^{4}x_{i}^{2}>0$, we have $\lambda\leq 4$. Combining with the conclusion of Proposition 8.1, we see that $\lambda(\mathcal{L})=4=\Delta+1$.