The smallest spectral radius of bicyclic uniform hypergraphs with a given size

Haiying Shan, Zhiyi Wang, Feifei Wang School of Mathematical Sciences, Tongji University, Shanghai 200092, China ([email protected])School of Mathematical Sciences, Tongji University, Shanghai 200092, China ([email protected])School of Mathematical Sciences, Tongji University, Shanghai 200092, China ([email protected])

Abstract

Identifying graphs with extremal properties is an extensively studied topic in spectral graph theory. In this paper, we study the log-concavity of a type of iteration sequence related to the $\alpha$ -normal weighted incidence matrices which is presented by Lu and Man for computing the spectral radius of hypergraphs. By using results obtained about the sequence and the method of some edge operations, we will characterize completely extremal $k$ -graphs with the smallest spectral radius among bicyclic hypergraphs with given size.

Keywords: Bicyclic hypergraph, Spectral radius, Weighted incidence matrix, Log-concave sequence.

AMS subject classification 2010: 05C65, 05C50, 15A18.

1 Introduction

A hypergraph $H=(V,E)$ consists of a set $V$ of vertices and a collection $E$ of subsets of $V$ . We call a member of $E$ a hyperedge or simple an edge of $H$ . A hypergraph $H$ is $k$ -uniform if all of its edges are $k$ -subsets of $V(H)$ . We also simply call a $k$ -uniform hypergraph a $k$ -graph for brevity. Throughout this paper, we focus on simple $k$ -uniform hypergraphs with $k\geq 3$ .

A hypergraph $H$ is a sub-hypergraph of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$ , and $H$ is a proper sub-hypergraph of $G$ if $V(H)\subsetneq V(G)$ or $E(H)\subsetneq E(G)$ .

Let $v$ be a vertex of $H$ . We use $E_{H}(v)$ to denote the set consisting of edges of $H$ which are incident to $v$ , also written as $E(v)$ for brevity. The cardinality of $E_{H}(v)$ is defined as the degree of the vertex $v$ , denoted $d_{H}(v)$ or $d(v)$ . A vertex of degree one is called a pendant vertex. For $e=(v_{1},v_{2},\ldots,v_{k})\in E(H)$ , if there exists at least $k-1$ pendant vertices, we say $e$ is a pendant vertex of $H$ ; if there exists at least one vertex of degree greater than 2 or three vertices of degree greater than 1, we say $e$ is a branch edge of $H$ .

In hypergraph theory, the most common definition of a cycle in a hypergraph is given by Berge (see [1]).

A Berge cycle of length $\ell$ is a hypergraph ${\mathcal{C}}$ consisting of $\ell$ distinct hyperedges $e_{1},...,e_{\ell}$ such that there exist $\ell$ distinct vertices $v_{1},\dots,v_{\ell}$ satisfying that $v_{i},v_{i+1}\in e_{i}$ for each $i=1,...,\ell-1$ and $v_{1},v_{\ell}\in e_{\ell}$ .

A Berge path of length $\ell$ is a hypergraph ${\mathcal{P}}$ consisting of $\ell$ distinct edges $e_{1},\dots,e_{\ell}$ such that there exist $\ell+1$ distinct vertices $v_{1},\dots,v_{\ell+1}$ satisfying that $v_{i},v_{i+1}\in e_{i}$ for $i=1,\ldots,\ell$ .

In graph theory, an internal path of a graph $G$ is a sequence of vertices $u_{1},\ldots,u_{n}$ such that all $u_{i}$ are distinct, except possibly $u1=u_{n}$ ; the vertex degrees satisfy $d(u_{1})\geq 3,d(u_{2})=\cdots=d(u_{n-1})=2,d(u_{n})\geq 3$ , and $u_{i}u_{i+1}\in E(G)$ for $i=1,\ldots,n-1$ .

Let $G=(V,E)$ be a simple graph. The $k$ -th power hypergraph of $G$ is the $k$ -uniform hypergraph resulting from adding $k-2$ new vertices to each edge of $G$ . For the ordinary path and cycle with $n$ edges, the $k$ -th power of them are called loose path and loose cycle with length $n$ , denoted by $\mathbb{P}_{n}$ and $\mathbb{C}_{n}$ , respectively.

In the following, we will give a general definition of internal path for hypergraph.

Definition 1.1.

For hypergraph $H$ , let $P=e_{0}v_{1}e_{1}v_{2}\cdots e_{n-1}v_{n}e_{n}$ be a vertex edge alternating sequence of $H$ such that $\mathbb{P}=v_{1}e_{1}v_{2}\cdots e_{n-1}v_{n}$ is a loose path of hypergraph $H$ and $d_{H}(v_{1})=d_{H}(v_{n})=2$ , $\{e_{0},e_{n}\}\subseteq E(H)$ (not necessarily distinct).

(1).

If $e_{0}$ and $e_{n}$ are both branch edges, then $P$ is called hyper-internal path of $H$ and $\mathbb{P}$ is called internal loose path.
(2).

If $P$ is a hyper-internal path and one of $e_{0}$ and $e_{n}$ contains no vertex with degree more than 2, then $P$ is called hypo-internal path of $H$ .

In graph theory, the cyclomatic number of connected graph $G$ is $|E(G)|-|V(G)|+1$ , which corresponds to the number of independent (in the sense of linear independence in the so-called cycle space) cycles in $G$ . In [2], Fan et al. present a generalization of cyclomatic number for $k$ -uniform graph. Let $H$ be a $k$ -graph with $n$ vertices, $m$ edges, and $p$ connected components. The cyclomatic number of $H$ is denoted as $c(H)$ and defined as $c(H)=m(k-1)-n+p$ . The connected hypergraph $H$ with $c=c(H)$ is called a $c$ -cyclic hypergraph. In particular, $0$ -cyclic hypergraph, $1$ -cyclic hypergraph, $2$ -cyclic hypergraph, are called supertree, unicyclic $k$ -graph, bicyclic $k$ -graph, respectively.

A very important topic on spectral hypergraph theory is the characterization of hypergraphs with extremal values of the spectral radius in a given class of hypergraphs. The spectral radii of hypertrees are well studied in the literatures, see [3, 4, 5]. In [6], Linyuan Lu and Shoudong Man research the connected hypergraphs with small spectral radii and present the $\alpha$ -normal labeling method for comparing the spectral radii of connected $k$ -graphs.

In [2, 7], hypergraphs that attain the largest spectral radii among all unicyclic and bicyclic k-graphs are investigated. Recently, Zhang et al. determine the uniform hypergraphs of size $m$ with the first two smallest spectral radii [8].

Motivating by the preceding work on maximizing and ordering spectral radius, we will consider spectral extremal problems for bicyclic hypergraphs with given size in this paper.

The remainder of this paper is organized as follows: In Section 2, we give some basic definitions and results for tensor and spectra of hypergraphs. In Section 3, a kind of iteration sequence of möbius transformation, which related with some weighted incidence matrix of hypergraph, is researched. We present an explicit expression of the sequence and some property on the convexity and log-concavity of the sequence is researched. In Section 4, effects on the spectral radius of hypergraph by graph operations are researched. In Section 5, the first smallest spectral radius of bicyclic hypergraph are determined.

2 Preliminaries

The definition of eigenvalues of a tensor was proposed in [9, 10], independently. Let ${\mathcal{A}}$ be an order $k$ dimension $n$ tensor. If there exists a number $\lambda\in\mathbb{C}$ and a nonzero vector $\mathbf{x}=(x_{1},x_{2},...,x_{n})^{T}\in\mathbb{C}^{n}$ such that

{\mathcal{A}}\mathbf{x}=\lambda\mathbf{x}^{[r-1]},

where $\mathbf{x}^{[r-1]}$ is a vector with $i$ -th entry $x_{i}^{r-1}$ , then $\lambda$ is called an eigenvalue of ${\mathcal{A}}$ , $\mathbf{x}$ is called an eigenvector of ${\mathcal{A}}$ corresponding to the eigenvalue $\lambda$ . The spectral radius of ${\mathcal{A}}$ is the maximum modulus of the eigenvalues of ${\mathcal{A}}$ , denoted by $\rho({\mathcal{A}})$ .

In 2012, Cooper and Dutle [11] defined the adjacency tensors for $k$ -uniform hypergraphs.

Definition 2.1 ([11]).

The adjacency tensor $\mathcal{A}(G)=(a_{i_{1}\dots i_{k}})$ of a $k$ -uniform hypergraph $G$ is defined to be an order $k$ dimension $n$ tensor with entries $a_{i_{1}\dots i_{k}}$ such that

a_{i_{1}\dots i_{k}}=\begin{cases}\frac{1}{(k-1)!}&\text{if $\{i_{1},i_{2},\dots,i_{k}\}\in E(G)$},\\ 0&\text{otherwise}.\end{cases}

The following result can be found in [11, 12] and will be used in the sequel.

Theorem 2.1.

Suppose that $H$ is a uniform hypergraph, and $H^{\prime}$ is a sub-hypergraph of $H$ . Then $\rho(H^{\prime})\leq\rho(H)$ . Furthermore, if in addition $H$ is connected and $H^{\prime}$ is a proper sub-hypergraph, we have $\rho(H^{\prime})<\rho(H)$ .

Definition 2.2.

[6] A weighted incidence matrix $B$ of a hypergraph $H$ is a $\mid V\mid\times\mid E\mid$ matrix such that for any vertex $v$ and edge $e$ , the entry $B(v,e)>0$ if $v\in e$ and $B(v,e)=0$ if $v\notin e$ .

Let ${\mathcal{C}}_{m}=v_{0}e_{1}v_{1}e_{2}\cdots e_{m}v_{m}$ ( $v_{0}=v_{m}$ ) be a Berge cycle of $H$ . For a weighted incidence matrix $B$ of $H$ , if

\prod_{i=1}^{m}\frac{B(v_{i},e_{i})}{B(v_{i-1},e_{i})}=1,

we say that $B$ is consistent with ${\mathcal{C}}_{m}$ . If $B$ is consistent for any Berge cycle of $H$ , we say that $B$ is consistent for $H$ .

Definition 2.3.

[6] A hypergraph $H$ is called $\alpha$ -supernormal if there exists a weighted incidence matrix B satisfying

(1).

$\sum\limits_{e\in E(v)}B(v,e)\geq 1$ , for any $v\in V(H)$ ,
(2).

$\prod\limits_{v\in e}B(v,e)\leq\alpha$ , for any $e\in E(H)$ .

If both equalities hold in above inequalities, $H$ is called $\alpha$ -normal. Otherwise, $H$ is called strictly $\alpha$ -supernormal. Furthermore, if $B$ is consistent, $H$ is called consistently $\alpha$ -supernormal.

Definition 2.4.

[6] A hypergraph $H$ is called $\alpha$ -subnormal if there exists a weighted incidence matrix B satisfying

(1).

$\sum\limits_{e\in E(v)}B(v,e)\leq 1$ , for any $v\in V(H)$ ,
(2).

$\prod\limits_{v\in e}B(v,e)\geq\alpha$ , for any $e\in E(H)$ .

If one of above inequalities is strict, $H$ is called strictly $\alpha$ -subnormal.

Theorem 2.2.

[6] Let $H$ be a connected $k$ -uniform hypergraph. Then the following results hold:

(1).

$\rho$ is the spectral radius of $H$ if and only if $H$ is consistently $\alpha$ -normal with $\alpha=\rho^{-k}$ .
(2).

If $H$ is $\alpha$ -subnormal, $\rho\leq\alpha^{-\frac{1}{k}}$ . Moreover, if $H$ is strictly $\alpha$ -subnormal, $\rho<\alpha^{-\frac{1}{k}}$ .
(3).

If $H$ is strictly and consistently $\alpha$ -supernormal, $\rho>\alpha^{-\frac{1}{k}}$ .

Lemma 2.1.

Let $H$ be a connected $k$ -uniform hypergraph, and $\mathbf{x}$ be the principal eigenvector of $H$ . Define the weighted incidence matrix $B$ such that

B(v,e)=\begin{cases}\displaystyle(\prod_{i\in e}\frac{x_{i}}{x_{v}})\rho(H)^{-1}&\text{ if }v\in e,\\ 0&\text{otherwise.}\end{cases}

Then $H$ is consistently $\alpha$ -normal, where $\alpha(H)=\rho(H)^{-k}$ .

In the sequel, the weighted incidence matrix of hypergraph $H$ defined in Lemma 2.1 is denoted by $B_{H}$ .

Definition 2.5.

Let $\mathbb{P}$ be an internal path of length $n$ between $w_{0}$ and $w_{n}$ in hypergraph $H$ . Let $e_{1},e_{n}\in E(\mathbb{P})$ and $w_{0}\in e_{1},w_{n}\in e_{n}$ , $B$ is a weighted incidence matrix of $H$ . Write $x=B(w_{0},e_{1}),y=B(w_{n},e_{n})$ .

We say that $B$ is $(x,y)$ $\alpha$ -normal on $\mathbb{P}$ , if $B$ satisfies the following conditions:

(1).

$\sum\limits_{e\in E(v)}B(v,e)=1$ , for any $v\in V(\mathbb{P})\setminus\{w_{0},w_{n}\}$ ,
(2).

$\prod\limits_{v\in e}B(v,e)=\alpha$ , for any $e\in E(\mathbb{P})$ .

Lemma 2.2.

Let $e^{\prime}=(u_{1},u_{2},\dots,u_{k}),e^{\prime\prime}=(v_{1},v_{2},\dots,v_{k})$ be two edges of $k$ -uniform hypergraph $H$ and $B$ be a weighted incidence matrix of $H$ .

(1).

Let $P_{1}$ is a $(u_{1},u_{2})$ - internal loose path of $H$ . If $B$ is $(x_{0},x_{0})$ $\alpha$ -normal for $P_{1}$ and $B(u_{1},e^{\prime})=B(u_{2},e^{\prime})=1-x_{0}$ , then $B$ is consistent for cycle $u_{1}P_{1}u_{2}e^{\prime}u_{1}$ .
(2).

Let $P_{1}$ is a $(u_{1},v_{1})$ - internal loose path and $P_{2}$ is a $(u_{2},v_{2})$ - internal loose path of $H$ . For $i=1,2$ , if $B$ is $(y_{i},y_{i})$ $\alpha$ -normal for $P_{i}$ and $B(u_{i},e^{\prime})=B(v_{i},e^{\prime\prime})=1-y_{i}$ , then $B$ is consistent for cycle $u_{1}P_{1}v_{1}e^{\prime\prime}v_{2}P^{-1}_{2}u_{2}e^{\prime}u_{1}$ .

Proof.

(1). Suppose $P_{1}=w_{0}e_{1}w_{1}e_{2}w_{2}\cdots e_{n-1}w_{n-1}e_{n}w_{n}$ and $w_{0}=u_{1},w_{n}=u_{2}$ . Let $x_{i}=B(w_{i},e_{i+1}),x^{\prime}_{i}=B(w_{i},e_{i})$ ( $i=1,2,\ldots,n-1$ ) and $x_{0}=B(w_{0},e_{1})$ , $x^{\prime}_{n}=B(w_{n},e_{n})$ . Since $B$ is $(x_{0},x_{0})$ $\alpha$ -normal for $P_{1}$ , we have $x^{\prime}_{n-j}=x_{j}$ for any $j\in\{0,1,\ldots,n\}$ .

For Berge cycle $u_{1}P_{1}u_{2}e^{\prime}u_{1}=w_{0}e_{1}w_{1}e_{2}w_{2}\cdots e_{n-1}w_{n-1}e_{n}w_{n}e^{\prime}w_{0}$ , we have

\frac{B(w_{0},e^{\prime})}{B(w_{n},e^{\prime})}\prod_{i=1}^{n}\frac{B(w_{i},e_{i})}{B(w_{i-1},e_{i})}=1.

So $B$ is consistent for cycle $u_{1}P_{1}u_{2}e^{\prime}u_{1}$ .

(2). Using similar arguments the result can be deduced from the conditions. ∎

3 On a kind of sequence obtained by iteration of Möbius transform

In this section, we will focus on the convexity and log-concavity of some sequences which are related with the $\alpha$ -normal weighted incidence matrices of hypergraphs. Proposition 3.1 of this section will play a key role in the proof of our main result (Theorem 5.4) of this paper.

Let $H$ be a connected $k$ -graph and $\mathbb{P}_{n}=w_{0}e_{1}w_{1}e_{2}w_{2}\cdots e_{n-1}w_{n-1}e_{n}w_{n}$ be a loose path in $k$ -graph $H$ . Let $B$ be a $\alpha$ -normal weighted incidence matrix. Take $x_{i}=B(w_{i},e_{i+1})$ ( $i=0,1,\dots,n-1$ ) and $\displaystyle x_{n}=\sum_{e\in E_{H}(v)\setminus\{e_{n}\}}B(v,e)$ . Then we have: $x_{i}(1-x_{i+1})=\alpha$ for $i=0,\dots,n-1$ .

Hence, $(x_{i})_{i=0}^{n}$ is finite portion of the following bi-infinite sequence $(x_{i})_{i\in\mathbb{Z}}$ such that

x_{n}=f(x_{n-1})=f^{n}(x_{0})\text{ for }n\in\mathbb{Z},

(3.1)

where $f(x)=1-\frac{\alpha}{x}$ , which is a special type of Möbius transform (see Section 1.2 of [13]).

$\phi(x)=x^{2}-x+\alpha=0$ is called characteristic equation of the iterative sequence $(x_{i})$ . The roots of $\phi(x)=0$ are called the characteristic roots of the sequence $(x_{i})$ .

When $0<\alpha<\frac{1}{4}$ , $\phi(x)$ have two distinct positive roots, denoted by $r_{1},r_{2}$ . Suppose $r_{2}<r_{1}$ . Let $\theta=\operatorname{arcosh}(\frac{1}{2}\alpha^{-\frac{1}{2}})$ . Then $r_{1},r_{2}$ can be written in the following form:

r_{1}=\sqrt{\alpha}e^{\theta},\qquad r_{2}=\sqrt{\alpha}e^{-\theta}.

Since $1-4\alpha=1-sech^{2}(\theta)=\tanh^{2}(\theta)$ , $r_{1},r_{2}$ can be rewritten as:

r_{2}=\frac{1}{2}(1-\tanh(\theta)),\qquad r_{1}=\frac{1}{2}(1+\tanh(\theta)).

For sequence (3.1), if there exists some integer $j$ such that $x_{j}=\alpha$ , then $x_{j+1}=0$ , $x_{j+2}=-\infty$ and $x_{j+3}=1$ .

If the sequence (3.1) is positive sequence and there exist integers $p,q$ such that $x_{p}+x_{q}=1$ , we call that $(x_{i})$ is symmetric.

It is obvious that $(x_{i})$ is symmetric when $x_{0}=\frac{1}{2},\alpha=\frac{1}{4}$ .

Lemma 3.1.

Let $(x_{i})_{i\in\mathbb{Z}}$ be the sequence mentioned above.

(1).

If $\alpha\in(0,\frac{1}{4}]$ and $x_{0}\in(0,1]$ , then

x_{n}=\frac{2\cosh(\theta)\sinh((n+1)\theta)x_{0}-\sinh(n\theta)}{2\cosh(\theta)\big{(}2\cosh(\theta)\sinh(n\theta)x_{0}-\sinh((n-1)\theta)\big{)}},

where $\theta=\operatorname{arcosh}(\frac{1}{2}\alpha^{-\frac{1}{2}})$ .

(2).

If $\phi(x_{0})<0$ , then $(x_{i})_{i\in\mathbb{Z}}$ is strictly increasing and $\displaystyle\lim_{i\to\infty}x_{i}=r_{1}$ .
(3).

If $x_{0}>r_{1}$ , then $(x_{i})_{i\in\mathbb{Z}}$ is strictly decreasing and $\displaystyle\lim_{i\to\infty}x_{i}=r_{1}$ .
(4).

If $x_{0}<r_{2}$ , then there exists $n_{0}>0$ such that $x_{n_{0}}\leq 0$ and $(x_{i})_{i=0}^{n_{0}-1}$ is positive decreasing sequence.

Proof.

(1). When $\alpha=\frac{1}{4}$ , $\theta=0$ , for any integer $n$ , $x_{n}=\frac{1}{2}.$ The result holds.

When $\alpha\neq\frac{1}{4}$ , as mentioned above, $r_{1},r_{2}$ be characteristic roots of sequence $(x_{n})_{n\in\mathbb{Z}}$ . By the formula (8) of [14], we have:

	$\displaystyle x_{n}=$	$\displaystyle\frac{(r_{1}^{n+1}-r_{2}^{n+1})x_{0}-r_{1}r_{2}(r_{1}^{n}-r_{2}^{n})}{(r_{1}^{n}-r_{2}^{n})x_{0}-r_{1}r_{2}(r_{1}^{n-1}-r_{2}^{n-1})}$
	$\displaystyle=$	$\displaystyle\frac{2\cosh(\theta)\sinh((n+1)\theta)x_{0}-\sinh(n\theta)}{2\cosh(\theta)\big{(}2\cosh(\theta)\sinh(n\theta)x_{0}-\sinh((n-1)\theta)\big{)}}.$

(2). Since $\phi(x_{i})<0$ , $\phi(x)=0$ have two distinct positive roots, denoted by $r_{1},r_{2}$ as before. So $r_{2}<x_{i}<r_{1}$ . Because $f(x),f^{-1}(x)$ are strictly increasing functions in the interval $(0,\infty)$ , we have

r_{2}=f(r_{2})<f(x_{i})<f(r_{1})=r_{1},

r_{2}=f^{-1}(r_{2})<f^{-1}(x_{i})<f^{-1}(r_{1})=r_{1}.

Therefore, $r_{2}<x_{i-1}<r_{1}$ and $r_{2}<x_{i+1}<r_{1}$ .

So $\forall j\in\mathbb{Z}$ , $r_{2}<x_{j}<r_{1}$ , $\phi(x_{j})<0$ . $x_{j}-f(x_{j})<0$ follows.

Since $x_{j+1}=f(x_{j})$ , we have $x_{j}<x_{j+1}$ for any $j\in\mathbb{Z}$ .

Hence, $(x_{i})$ is strictly increasing bounded sequence. And $\displaystyle\lim_{i\to+\infty}x_{i}$ exists. Suppose $\displaystyle\lim_{i\to+\infty}x_{i}=z$ . It is clear that $z>r_{2}$ . Next, we take limits as $i\to\infty$ on both sides of $x_{i+1}=f(x_{i})$ . We have $z=1-\frac{\alpha}{z}$ . So $z$ is a root of $\phi(x)=0$ . Since $z>r_{2}$ , $z=r_{1}$ follows. That is, $\displaystyle\lim_{i\to\infty}x_{i}=r_{1}$ .

(3) If $x_{i}>r_{1}$ , then $\phi(x_{i})>0$ and $x_{i}>f(x_{i})=x_{i+1}>r_{1}$ . So $(x_{i})_{i=0}^{+\infty}$ is a decreasing bounded positive sequence. So $\displaystyle\lim_{i\to\infty}x_{i}$ exists, denoted by $r$ . Furthermore, $r$ will be a root of $\phi(x)=0$ . From $x_{0}>r_{1}$ , we have $r\geq r_{1}$ . Since $r_{1}$ is the maximal root of $\phi(x)$ , we have $r=r_{1}$ .

(4) If $0<x_{i}<r_{2}$ , then $\phi(x_{i})>0$ and $x_{i}>f(x_{i})=x_{i+1}$ . There must exist $n_{0}>0$ such that $x_{n_{0}}\leq 0$ . Otherwise, $(x_{i})_{i=0}^{+\infty}$ is a bounded positive sequence. So $\displaystyle\lim_{i\to\infty}x_{i}$ exists, denoted by $r$ . Furthermore, $r$ will be a root of $\phi(x)=0$ . From $x_{0}<r_{2}$ , we have $r<r_{2}$ , which contradicts that $r_{2}$ is the minimal root of $\phi(x)$ . The result follows.∎

Let

\displaystyle F(n,x_{0})=

\displaystyle\frac{2\cosh(\theta)\sinh((n+1)\theta)x_{0}-\sinh(n\theta)}{2\cosh(\theta)\big{(}2\cosh(\theta)\sinh(n\theta)x_{0}-\sinh((n-1)\theta)\big{)}}.

For the sake of brevity, take $p(n)=2\cosh(\theta)\sinh((n+1)\theta)x_{0}-\sinh(n\theta).$ Then

F(n,x_{0})=\frac{p(n)}{2\cosh(\theta)p(n-1)}.

Suppose the sequence $(x_{i})_{i\in\mathbb{Z}}$ is symmetric. Without loss of generality, suppose $x_{p}+x_{q}=1$ ( $p=q+l\in\mathbb{Z}$ , $l\geq 0$ ). Take $y_{i}=x_{i-q}$ . Then $(y_{i})_{i\in\mathbb{Z}}$ is an iteration sequence of $f(x)=1-\frac{\alpha}{x}$ with initial value $y_{0}$ . By (1) of Lemma 3.1, we have $y_{n}=F(n,y_{0})$ for all $n\in\mathbb{Z}$ .

For $x_{p}+x_{q}=1$ , $y_{0}+y_{l}=1$ . So $y_{0}+F(l,y_{0})=1$ . Namely, $y_{0}$ is a root of the equation $x+F(l,x)=1$ .

Furthermore, we have the following conclusion:

Theorem 3.1.

Let $(y_{i})_{i\in\mathbb{Z}}$ be the symmetric sequence mentioned as above.

(1).

For any $s\in\mathbb{Z}$ , we have $y_{l+s}+y_{-s}=1$ .
(2).

If $0<\alpha<\frac{1}{4}$ , then $(y_{i})_{i\in\mathbb{Z}}$ is strictly increasing bounded sequence with $r_{2}<y_{i}<r_{1}$ for any $i$ and $\displaystyle\lim_{i\to+\infty}y_{i}=r_{1}$ .
(3).

For $0<\alpha<\frac{1}{4}$ , $y_{0}$ is the largest root of $x+F(l,x)=1$ and

$y_{0}=\frac{1}{2}\bigg{(}1-\tanh(\theta)\tanh\left(\frac{l\theta}{2}\right)\bigg{)}.$

Proof.

(1). It is sufficient to show that if there exist integers $p,q$ such that $y_{p}+y_{q}=1$ , then $y_{p+1}+y_{q-1}=1$ .

For $f(x)=1-\frac{\alpha}{x}$ , we have
$y_{p+1}=f(y_{p})=1-\frac{\alpha}{y_{p}},y_{q-1}=f^{-1}(y_{q})=\frac{\alpha}{1-y_{q}}=\frac{\alpha}{y_{p}}$ . So $y_{p+1}+y_{q-1}=1$ .
Since $y_{0}+y_{l}=1$ , $y_{l+s}+y_{-l}=1$ holds for any $s\in\mathbb{Z}$ .

(2). Take $t=\lfloor\frac{l}{2}\rfloor$ . From (1), $y_{l-t}+y_{t}=1$ holds. So

y_{t}=\begin{cases}\sqrt{\alpha}&\text{ if $l$ is odd},\\ \frac{1}{2}&\text{otherwise}.\end{cases}

Hence, $r_{2}<\sqrt{\alpha}<\frac{1}{2}<r_{1}$ and $\phi(y_{t})<0$ .

The result follows from (2) of Lemma 3.1.

(3). Since $y_{0}$ is a root of $x+F(l,x)=1$ , By (1) of Lemma 3.1, $y_{0}$ is a root of the following equation:

\frac{2\cosh(\theta)\sinh((l+1)\theta)x-\sinh(l\theta)}{2\cosh(\theta)\big{(}2\cosh(\theta)\sinh(l\theta)x-\sinh((l-1)\theta)\big{)}}+x=1,

which has the same roots as the following quadratic equation

x^{2}-\frac{\sinh((l-1)\theta)}{\sinh(l\theta)\cosh(\theta)}x+\frac{\sinh((l-2)\theta))}{4\sinh(l\theta)\cosh^{2}(\theta)}=0.

Let $\Delta$ be the discriminant of above quadratic equations. Then

\sqrt{\Delta}=\frac{\sqrt{\sinh^{2}((l-1)\theta)-\sinh(l\theta)\sinh((l-2)\theta)}}{\sinh(l\theta)\cosh(\theta)}=\frac{\sinh(\theta)}{\sinh(l\theta)\cosh(\theta)}.

By the quadratic formula we obtained the two roots of above equation:

\nu_{0}=\frac{\sinh((l-1)\theta)-\sinh(\theta)}{2\sinh(l\theta)\cosh(\theta)},\quad\nu_{1}=\frac{\sinh((l-1)\theta)+\sinh(\theta)}{2\sinh(l\theta)\cosh(\theta)}.

Next, we will complete the proof of (2) by showing that $y_{0}=\nu_{1}$ .

Since $r_{2}<y_{0}<r_{1}$ , to show $y_{0}=\nu_{1}$ , it is efficient to prove that $\nu_{0}<r_{2}$ .

Since $r_{2}=\frac{1}{2}(1-\tanh(\theta))$ , we have

		$\displaystyle\nu_{0}<r_{2}$
	$\displaystyle\iff$	$\displaystyle\sinh((l-1)\theta)-\sinh(\theta)<(\cosh(\theta)-\sinh(\theta))\sinh(l\theta)$
	$\displaystyle\iff$	$\displaystyle-\sinh(\theta)<(\cosh(l\theta)-\sinh(l\theta))\sinh(\theta).$

Since $\theta=\operatorname{arcosh}(\frac{1}{2}\alpha^{-\frac{1}{2}})>0$ , the last condition holds. So

y_{0}=\nu_{1}=\frac{\sinh((l-1)\theta)+\sinh(\theta)}{2\sinh(l\theta)\cosh(\theta)}.

This formula can be rewritten as

y_{0}=\frac{1}{2}(1-\tanh(\theta)\tanh(\frac{l\theta}{2})).\qed

In the sequel, we always write

F_{0}(x)=\frac{1}{2}(1-\tanh(\theta)\tanh(\frac{x\theta}{2}))

and

F_{0}^{*}(x)=1-F_{0}(x)=\frac{1}{2}(1+\tanh(\theta)\tanh(\frac{x\theta}{2})).

Consequently, $y_{0}=F_{0}(l)=F_{0}^{*}(-l)$ and $F_{0}(x)=F_{0}^{*}(-x)$ .

From (1) and (3) of Theorem 3.1, we have

y_{-s}=F_{0}(l+2s).

(3.2)

Furthermore, we have the following Corollary.

Corollary 3.1.

$(x_{i})_{i\in\mathbb{Z}}$ is the symmetric sequence defined as (3.1). Without loss of generality, suppose $x_{p}+x_{q}=1$ ( $l\geq 0,p=q+l\in\mathbb{Z}$ ). Then
for $\alpha\in(0,\frac{1}{4}]$ , $x_{n}$ can be expressed as:

x_{n}=F^{*}_{0}(2n-p-q).

Proof.

Take $y_{i}=x_{i-q}$ . Then $(y_{i})_{i\in\mathbb{Z}}$ is the iteration sequence of $f(x)=1-\frac{\alpha}{x}$ with initial value $y_{0}$ . Since $x_{p}+x_{q}=1$ , $y_{0}+y_{l}=1$ .

By (3.2), we have

x_{n}=y_{n-q}=F_{0}(l-2(n-q))=F_{0}(p+q-2n)=F_{0}^{*}(2n-p-q).\qed

The remainder of this section is dedicated to the study of the convexity of $F_{0}(x)$ and the log-concavity of $F_{0}^{*}(x)$ .

Definition 3.1.

A function $f$ is log-concave on $I\subseteq\mathbb{R}$ , if $f(x)\geq 0$ for all $x\in I$ and the function $x\mapsto logf(x)$ is concave on $I$ .

It is well known (see [15]) that

Theorem 3.2.

Let $F$ be positive function on $I\in\mathbb{R}$ . Then the function

\varphi\left(x_{1},\ldots,x_{n}\right)=\prod_{i=1}^{n}F\left(x_{i}\right)

is Schur-concave if and only if $F$ is log-concave.

Theorem 3.3.

Let $F_{0}(x)$ and $F_{0}^{*}(x)$ be as defined above, then

(1).

$F_{0}(x)$ is strictly decreasing and convex in the interval $(0,+\infty)$ ;
(2).

$F_{0}^{*}(x)$ is strictly increasing and concave in $(0,+\infty)$ and log-concave in $[-1,+\infty)$ .

Proof.

(1). For $F_{0}(n)=\frac{1}{2}(1-\tanh(\theta)\tanh(\frac{n\theta}{2}))$ , by simple computation, we have

F_{0}(x)^{\prime}=-\frac{\theta}{4}\tanh(\theta)\operatorname{sech}^{2}(\frac{x\theta}{2})

and

F_{0}(x)^{\prime\prime}=\frac{\theta^{2}}{4}\tanh(\theta)\tanh(\frac{x\theta}{2})\operatorname{sech}^{2}(\frac{x\theta}{2}).

Since $\theta>0$ , $F_{0}(x)^{\prime}<0$ and $F_{0}(x)^{\prime\prime}>0$ on $(0,+\infty)$ . So $F_{0}(x)$ is strictly decreasing and convex in the interval $(0,+\infty)$ .

(2). Since $F_{0}^{*}(x)=1-F_{0}(x)$ , from (1), it follows that $F_{0}^{*}(x)$ is strictly increasing and concave in the interval $(0,+\infty)$ .

Since

	$\displaystyle F^{*}_{0}(x)$	$\displaystyle=\frac{\sinh((x+1)\theta)-\sinh(\theta)}{2\sinh(x\theta)\cosh(\theta)}$
		$\displaystyle=\frac{1}{2}(1+\tanh(\theta)\tanh(\frac{x\theta}{2})).$

Let $f^{*}(x)=log(F^{*}_{0}(x))$ . We have

f^{*}(x)^{\prime}=\frac{\theta{(\cosh(\theta x)-1)}\sinh(\theta)}{{(\sinh(\theta{(x+1)})-\sinh(\theta))}\sinh(\theta x)}=\frac{\theta\sinh(\theta)\tanh(\frac{x\theta}{2})}{{(\sinh(\theta{(x+1)})-\sinh(\theta))}}

and

f^{*}(x)^{\prime\prime}=-\frac{(\theta\tanh(\frac{1}{2}\theta x))^{2}\sinh(\theta{(x+1)})\sinh(\theta)}{(\sinh(\theta{(x+1)})-\sinh(\theta))^{2}}.

For $\theta>0$ , $x>-1$ , we have $f^{*}(x)^{\prime\prime}<0$ . So $F_{0}^{*}(x)$ is log-concave in $[-1,+\infty)$ . ∎

Proposition 3.1.

Suppose $a,b,c,d$ are real numbers such that $0\leq a<b\leq c<d$ , then

(1).

If $a+d=b+c$ , we have $F_{0}^{*}(a)F_{0}^{*}(d)<F_{0}^{*}(b)F_{0}^{*}(c)$ ;
(2).

$F_{0}^{*}(b)F_{0}^{*}(-a)<F_{0}^{*}(0)F_{0}^{*}(b-a)$ .

Proof.

(1). From (2) of Theorem 3.3 and Theorem 3.2, the assertion (1) holds.

(2). From $F_{0}^{*}(-x)+F_{0}^{*}(x)=1$ and $0\leq F_{0}^{*}(-x),F_{0}^{*}(x)<1$ , we have $F_{0}^{*}(a)F_{0}^{*}(-a)\leq(\frac{F_{0}^{*}(a)+F_{0}^{*}(-a)}{2})^{2}=\frac{1}{4}$ .

Using (2) of Theorem 3.3 and Theorem 3.2, we have
$F_{0}^{*}(b)=2F_{0}^{*}(0)F_{0}^{*}(b)<2F_{0}^{*}(b-a)F_{0}^{*}(a)$ .

	$\displaystyle F_{0}^{}(b)F_{0}^{}(-a)$	$\displaystyle<2F_{0}^{}(b-a)F_{0}^{}(a)F_{0}^{*}(-a)$
		$\displaystyle<\frac{1}{2}F_{0}^{}(b-a)=F_{0}^{}(0)F_{0}^{*}(b-a).$

The assertion (2) holds. ∎

4 The effect on the spectral radii of uniform hypergraphs by some graph operations

In the study of spectral graph theory, the effects on the spectrum are observed when some operations, such as edge moving, edge subdividing, are applied to the graph. In this section, we study the effects on spectral radii of $k$ -graphs under the operations:vertex-splitting and vertex-releasing operations.

Definition 4.1 (Edge moving operation [16]).

For $k\geq 2$ , let $G$ be a $k$ -uniform hypergraph with $u,v_{1},\dots,v_{r}\in V(G)$ and $e_{1},\dots,e_{r}\in E(G)$ for $r\geq 1$ such that $u\notin e_{i}$ and $v_{i}\in e_{i}$ for $i=1,\dots,r$ , where $v_{1},\dots,v_{r}$ are not necessarily distinct. Let $e^{\prime}_{i}=(e_{i}\backslash\{v_{i}\})\cup\{u\}$ for $i=1,\dots,r$ . Suppose that $e^{\prime}_{i}\notin E(G)$ for $i=1,\dots,r$ . Let $G^{\prime}=G-\{e_{1},\dots,e_{r}\}+\{e^{\prime}_{1},\dots,e^{\prime}_{r}\}$ . Then we say that $G^{\prime}$ is obtained from $G$ by moving edges $(e_{1},\ldots,e_{r})$ from $(v_{1},\ldots,v_{r})$ to $u$ .

The following Lemma is a special case of Corollary 2.1 in [16].

Lemma 4.1.

Let $u_{1},u_{2}$ are non-pendant vertices in an edge of connected uniform hypergraph $H$ with $|E_{H}(u_{i})\setminus(E_{H}(u_{1})\cap E_{H}(u_{2}))|\geq 1$ for $i=1,2$ . Let $H^{\prime}$ be the hypergraph obtained from $H$ by moving edges $E_{H}(u_{2})\setminus(E_{H}(u_{1})\cap E_{H}(u_{2}))$ from $u_{2}$ to $u_{1}$ and $H\ncong H^{\prime}$ , then

\rho(H)<\rho(H^{\prime}).

Corollary 4.1.

Let $H$ be a connected $k$ -graph, $E_{H}(v)=\{e_{1},e_{2},\ldots,e_{s}\}$ ( $s\geq 3$ ), $u\in e_{2}$ and $d_{H}(u)=1$ . Take $H^{\prime}=H-e_{1}+e^{\prime}_{1}$ , where $e^{\prime}_{1}=e_{1}-\{v\}+\{u\}$ . Then $\alpha(H^{\prime})>\alpha(H)$ .

Proof.

Since $u$ and $v$ are vertices with degree at least 2 in $H^{\prime}$ . Let $H^{\prime}$ be the hypergraph obtained by moving $e^{\prime}$ from $u$ to $v$ , then $H^{\prime}\cong H$ . By Lemma 4.1, we have $\alpha(H^{\prime})>\alpha(H)$ . ∎

Definition 4.2 (vertex-splitting operation).

Let $w$ be a vertex of a hypergraph $H$ and $H^{\prime}$ be the hypergraph obtained by replacing $w$ with an edge $e=(u_{1},u_{2},\dots,u_{k})$ in such a way that some vertices adjacent to $w$ are now adjacent to $u_{1}$ and the rest are adjacent to $u_{k}$ . $d_{H^{\prime}}(u_{1})+d_{H^{\prime}}(u_{k})=d_{H}(w)+2$ and $d_{H^{\prime}}(u_{2})=\cdots=d_{H^{\prime}}(u_{k-1})=1$ . Then $H^{\prime}$ is said to be obtained from $H$ by splitting vertex $w$ .

Lemma 4.2.

Let $w$ be a vertex with degree 2 of connected $k$ -graph $H$ . Suppose $E_{H}(w)=\{e_{1},e_{2}\}$ and $H^{\prime}$ be the $k$ -graph obtained from $H$ by splitting vertex $w$ . Let $\alpha=\alpha(H),\phi(x)=x^{2}-x+\alpha$ . If $\phi(B_{H}(w,e_{1}))<0$ , then
$\alpha(H)<\alpha(H^{\prime})$ and $\rho(H^{\prime})<\rho(H)$ .

Proof.

Suppose that $e^{\prime}_{1},e^{\prime}_{2}$ are new edges obtained from $e_{1}$ and $e_{2}$ and $e_{0}=(u_{1},u_{2},\dots,u_{k})$ be the new edge of $H^{\prime}$ which obtained from $w$ during the process of splitting vertex $w$ . Then $e^{\prime}_{1}=(e_{1}\setminus\{w\})\cup\{u_{1}\}$ and $e^{\prime}_{2}=(e_{2}\setminus\{w\})\cup\{u_{k}\}$ . Take $B$ be a weighted incidence matrix of $H^{\prime}$ such that

B(v,e)=\begin{cases}B_{H}(v,e)&\text{ for $e\not\in\{e_{0},e^{\prime}_{1},e^{\prime}_{2}\}$ and $v\not\in e_{0}\cup e^{\prime}_{1}\cup e^{\prime}_{2}$},\\ B_{H}(v,e)&\text{ for $e\in\{e^{\prime}_{1},e^{\prime}_{2}\}$ and $v\in(e^{\prime}_{1}\cup e^{\prime}_{2})\setminus\{u_{1},u_{k}\}$},\\ B_{H}(w,e_{1})&\text{ for $(v,e)\in\{(u_{1},e^{\prime}_{1}),(u_{k},e_{0})\}$},\\ B_{H}(w,e_{2})&\text{ for $(v,e)\in\{(u_{k},e^{\prime}_{2}),(u_{1},e_{0})\}$},\\ 1&\text{ for $(v,e)\in\{(u_{i},e_{0})\mid 2\leq i\leq k-1\}$.}\end{cases}

Then $\forall v\in V(H^{\prime})$ and $\forall e\in E(H^{\prime})\setminus\{e_{0}\}$ , we have

\sum_{e\in E_{H^{\prime}}(v)}B(v,e)=1\text{ and }\prod_{v\in e}B(v,e)=\alpha.

Since $B_{H}(w,e_{1})+B_{H}(w,e_{2})=1,\phi(B_{H}(w,e_{1}))<0$ , $B_{H}(w,e_{1})B_{H}(w,e_{2})>r_{1}r_{2}=\alpha$ holds. Consequently, $\displaystyle\prod_{v\in e_{0}}B(v,e_{0})=B_{H}(w,e_{1})B_{H}(w,e_{2})>\alpha$ .

So $H^{\prime}$ is $\alpha$ -subnormal. By (2) of Theorem 2.2, we have $\alpha(H)<\alpha(H^{\prime})$ and $\rho(H^{\prime})<\rho(H)$ . ∎

Proposition 4.1.

Let $e=(v_{1},v_{2},\ldots,v_{k})$ be an edge of connected $k$ -graph $H$ with $d(v_{1})\geq 2$ and $B$ be the $\alpha$ -normal weighted incidence matrix of $H$ , then

(1).

$\alpha\leq B(v_{1},e)\leq 1-\alpha$ ;
(2).

if $d(v_{1})\geq 2,d(v_{2})\geq 2,d(v_{3})\geq 2$ , then $B(v_{1},e)\geq\frac{\alpha}{(1-\alpha)^{2}}$ .

Proof.

(1). Let $e=(v_{1},v_{2},\ldots,v_{k})$ and $v_{1}\in e\cap e^{\prime}$ .
By the definition of $\alpha$ -normal weighted incidence matrix, we have:
$\prod_{i=1}^{k}B(v_{i},e)=\alpha$ and $0<B(v_{i},e)\leq 1$ .
So $\alpha\leq B(v_{1},e)$ . Similarly, $\alpha\leq B(v_{1},e^{\prime})$ .

Since $\displaystyle\sum_{e\in E_{H}(v)}B(v,e)=1$ , we have $B(v_{1},e)\leq 1-B(v_{1},e^{\prime})\leq 1-\alpha$ .

(2). From (1), we have
$\displaystyle B(e,v)=\frac{\alpha}{\prod\limits_{u\in e\setminus\{v\}}B(u,e)}\geq\frac{\alpha}{B(v_{2},e)B(v_{3},e)}\geq\frac{\alpha}{(1-\alpha)^{2}}$ . ∎

Let

\alpha^{*}=1/3(4-c^{1/3}-c^{-1/3})\approx 0.24512233,

where $c=(3\sqrt{69}+25)/2$ . Then $\alpha^{*}$ is the unique root of the following equations in the interval $(0,1)$ :

	$\displaystyle(1-x)^{5}=x,$
	$\displaystyle(1-x)^{2}+(1-x)^{3}=1,$
	$\displaystyle x-(1-x)^{2}+(1-x)^{4}=0,$		(4.1)
	$\displaystyle\left(\frac{1}{2}(1+\sqrt{1-4x})\right)^{2}(1-x)-x=0.$		(4.2)

Claim 1.

For $0<\alpha<\frac{1}{4}$ , take $r_{1}>r_{2}$ be the two roots of $\phi(x)=x^{2}-x+\alpha=0$ . We have

\frac{\alpha}{(1-\alpha)^{2}}>r_{2}\iff\alpha<\alpha^{*}.

Proof.

Since $0<\alpha<\frac{1}{4}$ , we have $r_{1}>\frac{1}{2}>\frac{\alpha}{(1-\alpha)^{2}}$ . Then

	$\displaystyle\frac{\alpha}{(1-\alpha)^{2}}>r_{2}$	$\displaystyle\iff\phi(\frac{\alpha}{(1-\alpha)^{2}})<0$
		$\displaystyle\iff\alpha-(1-\alpha)^{2}+(1-\alpha)^{4}<0.$

Since $\alpha^{*}$ is the unique root of equation (4.1) in the interval $(0,1)$ , the claim follows. ∎

Lemma 4.3.

Let $\mathbb{C}_{n}=v_{1}e_{1}v_{2}\cdots v_{n}e_{n}v_{1}$ be a loose cycle with vertex $u\in e_{n}$ and $d(u)=1$ . We use $\mathbb{C}^{*}_{n}$ , $\mathbb{C}^{{}^{\prime}}_{n}$ to denote the $k$ -graph obtained from $\mathbb{C}_{n}$ by attaching a pendent edge to vertex $u$ and $v$ , respectively. We have

\alpha(\mathbb{C}^{{}^{\prime}}_{n})<\alpha(\mathbb{C}^{*}_{n})<\alpha^{*}.

Proof.

Let $\alpha_{n}=\alpha(\mathbb{C}^{*}_{n})$ , $B=B_{\mathbb{C}^{*}_{n}}$ and $y_{i}=B(v_{i},e_{i})$ for $i=1,\dots,n$ .

Since $\mathbb{C}_{n}$ is a proper subgraph of $\mathbb{C}^{*}_{n}$ , we have $\alpha_{n}<\alpha(\mathbb{C}_{n})=\frac{1}{4}$ .

Then we have $y_{1}+y_{n}=1$ and $(y_{i})_{i=1}^{n}$ is a symmetric sequence. According to Theorem 3.1, $\phi(B(v_{1},e_{1})<0$ . Let $H$ be $k$ -graph obtained from $\mathbb{C}^{*}_{n}$ by splitting vertex $v_{1}$ . It is clear that $H\cong\mathbb{C}^{*}_{n+1}$ . By Lemma 4.2, we have $\alpha(\mathbb{C}^{*}_{n+1})>\alpha(\mathbb{C}^{*}_{n})$ . Namely, $(\alpha_{i})_{i=2}^{+\infty}$ is a strictly increasing bounded sequence. So $\displaystyle\lim_{i\to+\infty}\alpha_{i}$ exists. Suppose $\displaystyle\lim_{i\to+\infty}\alpha_{i}=\alpha$ . Let $\displaystyle\theta_{n}=\operatorname{arcosh}(\frac{1}{2}\alpha_{n}^{-\frac{1}{2}}),\theta=\lim_{n\to\infty}\theta_{n}$ . Because $B$ is the $\alpha_{n}$ -normal weighted incidence matrix of $\mathbb{C}_{n}^{*}$ , from Theorem 3.1 it follows that $\theta_{n}$ is the root of the following equation:

\frac{1}{4}\bigg{(}1+\tanh(\theta_{n})\tanh\left(\frac{(n-1)\theta_{n}}{2}\right)\bigg{)}^{2}(1-\alpha_{n})=\alpha_{n}.

We take limits as $i\to\infty$ on both sides of above equation. We get

\frac{1}{4}\bigg{(}1+\tanh(\theta)\bigg{)}^{2}(1-\alpha)=\alpha.

That is $r_{1}^{2}(1-\alpha)=\alpha$ , where $r_{1}$ is the largest root of $x^{2}-x+\alpha=0$ . From equation (4.2), we have $\alpha=\alpha^{*}$ . So $\alpha_{n}<\alpha^{*}$ . From Lemma 4.2, $\alpha(\mathbb{C}^{{}^{\prime}}_{n})<\alpha(\mathbb{C}^{*}_{n})$ . So

\alpha(\mathbb{C}^{{}^{\prime}}_{n})<\alpha(\mathbb{C}^{*}_{n})<\alpha^{*}.

This result follows.∎

Theorem 4.1.

Suppose $n\geq 0$ . Let $e^{\prime},e^{\prime\prime}$ be two edges of connected $k$ -graph $H$ and $w_{0}\in e^{\prime},w_{n}\in e^{\prime\prime},d_{H}(w_{0})=d_{H}(w_{n})=2$ , $e^{\prime},e^{\prime\prime}$ both contains at least three vertices with degrees exceeding 1. $\mathbb{P}_{n}$ is an internal path of $H$ between $w_{0}$ and $w_{n}$ . Let $H^{\prime}$ be a $k$ -graph obtained from $H$ by splitting vertex $w_{0}$ .
If $\alpha(H)<\alpha^{*}$ , then $\rho(H)<\rho(H^{\prime})$ .

Proof.

Suppose $\mathbb{P}_{n}=w_{0}e_{1}w_{1}e_{2}w_{2}\cdots e_{n-1}w_{n-1}e_{n}w_{n}$ .

Write $x_{i}=B(w_{i},e_{i+1}),x^{\prime}_{i}=B(w_{i},e_{i})$ for $i\in\{1,\ldots,n-1\}$ and
$x_{0}=B(w_{0},e_{1}),x_{n}=B(w_{n},e^{\prime\prime}),x^{\prime}_{0}=B(w_{0},e^{\prime}),x^{\prime}_{n}=B(w_{n},e_{n})$ . Take $\alpha=\alpha(H)$ . From Proposition 4.1, $\min(B(w_{0},e^{\prime}),B(w_{n},e^{\prime\prime}))\geq\frac{\alpha}{(1-\alpha)^{2}}$ .

Since $\alpha<\alpha^{*}$ , by Claim 1, we have
$x_{0}=B(w_{0},e_{1})=1-B(w_{0},e^{\prime})\leq 1-\frac{\alpha}{(1-\alpha)^{2}}<1-r_{2}=r_{1}$ .
Similarly, $x^{\prime}_{n}=B(w_{n},e_{n})<r_{1}$ .

According to Lemma 4.2, to complete the proof, it suffices to show $\phi(x_{0})<0$ . That is, $r_{1}>x_{0}>r_{2}$ .

On the contrary, suppose $x_{0}\leq r_{2}$ . By Lemma 3.1, $(x_{i})_{i=0}^{n}$ is decreasing. So $x_{n-1}\leq x_{0}\leq r_{2}$ . Since $x_{n-1}x^{\prime}_{n}=\alpha$ , $x^{\prime}_{n}=\frac{\alpha}{x_{n-1}}\geq\frac{\alpha}{r_{2}}=r_{1}$ , a contradiction. Hence, $r_{2}<x_{0}<r_{1}$ , $\phi(x_{0})<0$ . The result follows from Lemma 4.2. ∎

Definition 4.3 (Vertex-releasing operation).

Let $e$ be an edge of connected $k$ -graph $H$ and $v_{1},v_{2},\ldots,v_{s}$ ( $s\geq 2$ ) be all vertices with degrees at least 2 in $e$ . Take $e^{\prime}=(e\cup\{w_{1},\ldots,w_{t}\})\setminus\{v_{1},\ldots,v_{t}\}$ ( $1\leq t<s$ ), where $w_{1},\ldots,w_{t}$ are new vertices. Let $H^{\prime}$ be hypergraph such that $E(H^{\prime})=(E(H)\setminus\{e\})\cup\{e^{\prime}\}$ . We say that $H^{\prime}$ is obtained from $H$ by releasing vertex $v_{1},\ldots,v_{t}$ of $e$ .

Theorem 4.2.

Let $e$ be an edge of connected $k$ -graph $H$ and $v_{1},v_{2},\ldots,v_{s}$ ( $s\geq 2$ ) be all vertices with degrees at least 2 in $e$ . Take $H^{\prime}$ be $k$ -graph obtained from $H$ by releasing some vertices of $e$ . We have

\alpha(H^{\prime})>\alpha(H)\text{ and }\rho(H^{\prime})<\rho(H).

Proof.

Let $\alpha=\alpha(H)$ and $e^{\prime}=(e\cup\{w_{1},\ldots,w_{t}\})\setminus\{v_{1},\ldots,v_{t}\}$ .
Suppose $V(H^{\prime})=V(H)\cup\{w_{1},\ldots,w_{t}\}$ and $E(H^{\prime})=(E(H)\setminus\{e\})\cup\{e^{\prime}\}$ . Let $B_{H}$ be the consistently $\alpha$ -normal weighted incidence matrix of $H$ .

Take $B$ be a weighted incidence matrix of $H^{\prime}$ such that

B(u,f)=\begin{cases}B_{H}(u,f)&\text{ for $u\not\in\{w_{1},\ldots,w_{t}\}$ and $f\neq e^{\prime}$},\\ B_{H}(u,e)&\text{ for $u\not\in\{w_{1},\ldots,w_{t}\}$ and $f=e^{\prime}$},\\ B_{H}(v_{i},e)&\text{ for $f=e^{\prime}$ and $u=w_{i}$, $i\in\{1,\ldots,s\}$ }.\end{cases}\vspace*{-2pt}

Then, for any $f$ in $E(H^{\prime})$ , $\displaystyle\prod_{u\in f}B(u,f)=\alpha$ .
For any $u$ in $V(H^{\prime})\setminus\{v,w\}$ , $\displaystyle\sum_{f\in E_{H^{\prime}}(u)}B(u,f)=1$
and for $i\in\{1,\ldots,s\}$ ,
$\displaystyle\sum_{f\in E_{H^{\prime}}(v_{i})}B(v_{i},f)=1-B_{H}(v_{i},e)<1$ and $\displaystyle\sum_{f\in E_{H^{\prime}}(w_{i})}B(w_{i},f)=B(v_{i},e)<1$ .

Hence, $B$ is strictly $\alpha$ -subnormal weighted incidence matrix of $H^{\prime}$ .
The result follows from Theorem 2.2. ∎

Theorem 4.3.

Let $H$ be a connected $k$ -graph with $c(H)>0$ . If $H$ is not loose cycle, then $\alpha(H)<\alpha^{*}$ .

Proof.

Let $G$ be a minimal $c$ -cyclic subgraph of $H$ with $c>0$ .

Case 1. $G$ is a loose cycle.

When there exist a subgraph of $H$ isomorphic to one of the following two graphs: $\mathbb{C}_{n}^{*}$ and $\mathbb{C}_{n}^{{}^{\prime}}$ , where $n$ is some integer more than one, by Lemma 4.3, $\alpha(G)<\alpha^{*}$ . Otherwise, since $H$ is connected and is not loose cycle, there must exist $e\in E(H)$ such that $|e\cap V(G)|\geq 2$ . Let $H_{1}$ be hypergraph with $V(H_{1})=V(H)\cup e$ and $E(H_{1})=E(G)\cup\{e\}$ . A hypergraph $G_{1}$ can be obtained by application of vertex-releasing operation to vertices in $e$ of degree more than one of $H_{1}$ such that $G_{1}$ is isomorphic to $\mathbb{C}_{n}^{*}$ or $\mathbb{C}_{n}^{{}^{\prime}}$ . By Theorems 4.2, 2.2, we have $\alpha(H)\leq\alpha(G_{1})<\alpha(C^{*}_{0})<\alpha$ .

Case 2. $G$ is not loose cycle.
Since $c(H)>1$ , $G$ must be hypergraph with $E(G)=\{e_{1},e_{2}\}$ and $|e_{1}\cap e_{2}|\geq 3$ .

Write $p=|e_{1}\cap e_{2}|$ . Then we have $\alpha(H)\leq\alpha(G)=\frac{1}{2^{p}}<\alpha^{*}$ . ∎

By Theorems 4.1 and 4.3, the following corollary is immediate.

Corollary 4.2.

Let $H$ be a connected $k$ -graph with $c(H)>0$ and $v$ is a vertex with degree 2 of some internal path of $H$ . Let $H^{\prime}$ be a $k$ -graph obtained from $H$ by splitting vertex $w_{0}$ . Then $\rho(H)<\rho(H^{\prime})$ .

5 Extremal hypergraphs in $\mathscr{B}(m)$ with the smallest spectral radius

Let $H$ be a $c$ -cyclic hypergraph. The base of $H$ , denoted by $\widehat{H}$ , is the (unique) minimal $c$ -cyclic subgraph of $H$ . It is easy to see that $\widehat{H}$ can be obtained from $H$ by consecutively deleting pendent edges.

It is known that there are three types of bases of bicyclic graphs (see Fig. 1). $\infty(n_{1},n_{2})$ is obtained from two vertex-disjoint cycles $C_{n_{1}}$ and $C_{n_{2}}$ by identifying vertex $u$ of $C_{n_{1}}$ and vertex $v$ of $C_{n_{2}}$ , $\infty(n_{1},n_{2},n_{3})$ is obtained from two vertex-disjoint cycles $C_{n_{1}}$ and $C_{n_{2}}$ by joining vertex $u$ of $C_{n_{1}}$ and vertex $v$ of $C_{n_{2}}$ by a path $uu_{1}u_{2}\cdots u_{n_{3}-1}v$ of length $n_{3}(n_{3}\geq 1)$ , $\theta(n_{1},n_{2},n_{3})$ ( $n_{1}\geq n_{2}\geq n_{3}$ ) is obtained from three pairwise internal disjoint paths of lengths $n_{1},n_{2},n_{3}$ from vertices $u$ to $v$ . Note that $\infty(n_{1},n_{2},0)$ is exactly $\infty(n_{1},n_{2})$ .

The bicyclic graph containing $\theta(p,l,q)$ as its base is called a $\theta$ -graph.

For a hypergraph $H=(V,E)$ , we define the incidence graph to be the bipartite graph $K(H)$ with the vertex set $V\cup E$ and the edge set

\{(v,e):(v,e)\in V\times E,v\in e\}.

The graph $K(H)$ is also called the König representation of hypergraph $H$ .

It is easy to see that the number of Berge cycles of hypergraph $H$ and the number of cycles of its König representation $K(H)$ is same.

Proposition 5.1.

Let $H$ be a connected $k$ -uniform hypergraph, then $c(H)=c(K(H))$ .

Proof.

Suppose $H=(V,E)$ be a connected $k$ -uniform hypergraph with order $n$ and size $m$ . Since By the definition of $K(H)$ , we have $|V(K(H))|=m+n$ and $|E(K(H))|=km$ . So $c(K(H))=|E(K(H))|-|V(K(H))|+1=(k-1)m-n+1=c(H)$ . ∎

Inspired by the above result, the definition of the cyclomatic number for $k$ -graph can be generalized to general hypergraph as follows: The cyclomatic number of general hypergraph $H$ , denote by $c(H)$ , is defined as the cyclomatic number of the König representation of $H$ , namely $c(H)=c(K(H))$ .

Let $H$ be a $c$ -cyclic hypergraph and $H^{\prime}$ be hypergraph obtained by adding some new vertices with degree 1 to some edges of $H$ . It is obvious that $c(H)=c(H^{\prime})$ .

Let $H$ be a $k$ -graph and $e=\{u,u_{1},\ldots,u_{k-2},v\}$ be an edge of $H$ , where $d(u_{1})=\cdots=d(u_{k-2})=1$ . Subdividing an edge $e$ means replacing edge $e$ by two edges $f_{1}=\{u,u^{\prime}_{1},\ldots,u^{\prime}_{k-2},w\}$ and $f_{2}=\{w,u_{1},\ldots,u_{k-2},v\}$ , where $w,u^{\prime}_{1},\ldots,u^{\prime}_{k-2}$ are new added vertices.

Let $\mathscr{B}(m)$ denote the set consisting of all bicyclic $k$ -graphs with size $m$ . In the remaining part of this section, we will characterize the extremal hypergraph with the smallest spectral radius among bicyclic $k$ -graph with given size.

Let $\mathscr{C}(m)$ consist of all the minimal bicyclic $k$ -graphs ( $k\geq 3$ ) with edge number at most $m$ . Let $\mathscr{C}_{1}(m)=\{G\mid G\in\mathscr{C}(m),\Delta(G)=2\}$ , $\mathscr{C}_{2}(m)=\{G\mid G\in\mathscr{C}(m),\Delta(G)\geq 3\}$ .

Lemma 5.1.

Let $H$ be hypergraph in $\mathscr{B}(m)$ with the smallest spectral radius. Then $H$ is hypergraph in $\mathscr{C}_{1}(m)$ .

Proof.

Let $G$ be hypergraph in $\mathscr{C}(m)$ with the smallest spectral radius. We will show $G\in\mathscr{C}_{1}(m)$ with $|E(G)|=m$ .

Assume $G\in\mathscr{C}_{2}(m)$ . Since the König representation $K(G)$ is bicyclic graph, $\widehat{K(G)}$ is one of $\infty(n_{1},n_{2})$ , $\infty(n_{1},n_{2},n_{3})$ and $\theta(n_{1},n_{2},n_{3})$ and there exists vertex $v\in\widehat{K(G)}$ with $d_{\widehat{K(G)}}(v)\geq 3$ which is a vertex $u$ of $G$ with $d_{G}(u)\geq 3$ . Since $k\geq 3$ , there exist $e\in E(G)$ and $u,v\in e$ such that $d_{G}(u)=1$ and $d_{G}(v)\geq 3$ . From Corollary 4.1, there exists $k$ -graph ( $k\geq 3$ ) $G^{\prime}\in\mathscr{C}(m)$ with $|E(G^{\prime})|=m$ such that $\alpha(G^{\prime})>\alpha(G)$ . Namely, $\rho(G^{\prime})<\rho(G)$ , which is a contradiction to our assumption on $G$ . So $G\in\mathscr{C}_{1}(m)$ . If $|E(G)|<m$ , let $G^{\prime}$ be a hypergraph obtained by splitting some vertex $v$ with $d(v)=2$ . By Corollary 4.2, $\rho(G^{\prime})<\rho(G)$ and $|E(G^{\prime})|\leq m$ , a contradiction. So $|E(G)|=m$ and $G\in\mathscr{B}(m)\cap\mathscr{C}_{1}(m)$ .

Assume $H\not\in\mathscr{C}(m)$ . Then we have $\widehat{H}$ is proper subgraph of $H$ and $\widehat{H}\in\mathscr{C}(m)$ . By Theorem 2.1 we have $\rho(G)\leq\rho(\widehat{H})<\rho(H)$ , which is a contradiction to our assumption on $H$ since $G\in\mathscr{B}(m)$ . Therefore, $H$ is hypergraph in $\mathscr{C}_{1}(m)$ with size $m$ . ∎

Let $e^{\prime},e^{\prime\prime}$ be hyperedges with $|e^{\prime}|=|e^{\prime\prime}|=k\geq 3$ and $e^{\prime}\cap e^{\prime\prime}=\emptyset$ .

Take $U=\{u_{1},u_{2},u_{3}\},V=\{v_{1},v_{2},v_{3}\}$ such that $U\subseteq e^{\prime}$ , $V\subseteq e^{\prime\prime}$ . Let $n_{1},n_{2},n_{3}$ be non-negative integers. We denote by $C_{1}(n_{1},n_{2},n_{3})$ the $k$ -graph (See (a) of Fig. 3) obtained from $e^{\prime}$ and $e^{\prime\prime}$ by joining vertex pairs $(u_{1},u_{3})$ , $(v_{1},v_{3})$ and $(u_{2},v_{2})$ with three internal loose paths of lengths $n_{1},n_{2},n_{3}$ , respectively. $C_{1}(n_{1},n_{2},n_{3})$ is also referred to as $\infty$ -type hypergraph.

Let $C_{2}(n_{1},n_{2},n_{3})$ be the $k$ -graph (See (b) of Fig. 3) obtained from $e^{\prime}$ and $e^{\prime\prime}$ by joining vertex pairs $(u_{1},v_{1})$ , $(u_{2},v_{2})$ , $(u_{3},v_{3})$ with three internal loose paths of lengths $n_{1},n_{2},n_{3}$ , respectively. $C_{2}(n_{1},n_{2},n_{3})$ is also referred to as $\Theta$ -type hypergraph.

Let $u_{1},u_{2},v_{1},v_{2}$ be distinct vertices in hyperedge $e$ . We denote by $C_{3}(n_{1},n_{2})$ the $k$ -graph obtained from $e$ by joining vertex pairs $(u_{1},u_{2})$ , $(v_{1},v_{2})$ with two internal loose paths of lengths $n_{1},n_{2}$ , respectively. $C_{3}(n_{1},n_{2})$ is also referred to as $\Theta^{*}$ -type hypergraph.

Suppose $H\in\mathscr{C}_{1}(m)$ . Those vertices with degree more than 3 in $\widehat{K(H)}$ must be edges of $H$ . It is clear that

(1).

when $\widehat{K(H)}$ is isomorphic to some $\infty(p,q,r)$ ( $r\geq 1$ ), $H$ is $\infty$ -type $k$ -graph,
(2).

when $\widehat{K(H)}$ is isomorphic to some $\infty(p,q)$ , $H$ is $\Theta^{*}$ -type $k$ -graph,
(3).

when $\widehat{K(H)}$ is isomorphic to some $\theta(p,q,r)$ , $H$ is $\Theta$ -type $k$ -graph.

The bicyclic hypergraphs in $\mathscr{C}_{1}(m)$ can be partitioned into the following three sets:

	$\displaystyle\mathscr{B}_{1}(m)=$	$\displaystyle\{G\mid G\in\mathscr{B}(m)\text{ and }\widehat{G}\text{ is $\infty$-type $k$-graph}\},$
	$\displaystyle\mathscr{B}_{2}(m)=$	$\displaystyle\{G\mid G\in\mathscr{B}(m)\text{ and }\widehat{G}\text{ is $\Theta$-type $k$-graph}\},$
	$\displaystyle\mathscr{B}_{3}(m)=$	$\displaystyle\{G\mid G\in\mathscr{B}(m)\text{ and }\widehat{G}\text{ is $\Theta^{*}$-type $k$-graph}\}.$

Lemma 5.2.

For any positive integers $p,q$ , we have

\rho(C_{1}(p,p,q))=\rho(C_{2}(p,p,q)).

Proof.

Let $G=C_{1}(p,p,q),H=C_{2}(p,p,q)$ . Take $\alpha=\alpha(G)$ .
Suppose $B_{G}$ is the consistently $\alpha$ -normal weighted incidence matrix of $G$ , then we have $B_{G}(u_{1},e^{\prime})=B_{G}(u_{3},e^{\prime})=B_{G}(v_{1},e^{\prime\prime})=B_{G}(v_{3},e^{\prime\prime})$ .
Let $E_{G}(u_{1})=\{e^{\prime},e_{1}\},E_{G}(u_{3})=\{e^{\prime},e_{p}\}$ , $E_{G}(v_{1})=\{e^{\prime\prime},f_{1}\},E_{G}(v_{3})=\{e^{\prime\prime},f_{q}\}$ . Take $\tilde{e}_{1}=(e_{1}\cup\{v_{3}\})\setminus\{u_{1}\}$ , $\tilde{f}_{1}=(f_{1}\cup\{u_{3}\})\setminus\{v_{1}\}$ . Then $H\cong G\cup\{\tilde{e}_{1},\tilde{f}_{1}\}\setminus\{e_{1},f_{1}\}$ . By exchanging the values of $B_{G}(u_{1},e_{1})$ , $B_{G}(v_{3},e_{1})$ and $B_{G}(v_{1},f_{1})$ , $B_{G}(u_{3},f_{1})$ , respectively, a consistently $\alpha$ -normal weighted incidence matrix of $G$ is obtained from $B_{G}$ . Therefore, $\alpha(G)=\alpha(H)$ and $\rho(H)=\rho(G)$ . ∎

Theorem 5.1.

Let $p,q$ be positive integers such that $2p+q=m-2,|p-q|\leq 1$ . Then $C_{1}(p,p,q),C_{2}(p,p,q)$ are the extremal hypergraph with the smallest spectral radius in $\mathscr{B}_{1}(m),\mathscr{B}_{2}(m)$ , respectively.

Proof.

Suppose $H_{i}$ is the extremal hypergraph with the smallest spectral radius in $\mathscr{B}_{i}(m)$ . Then $H_{i}=(\widehat{H}_{i})$ ( $i=1,2$ ). Without loss of generality, Let $H_{i}=C_{i}(l_{1},l_{2},l_{3})$ . Take $H_{i}^{*}=C_{i}(p,p,q)$ , $\alpha=\alpha(H_{i}^{*})$ . Let $(y_{j})$ be the iterated sequence of $f(x)=1-\frac{\alpha}{x}$ with $y_{0}=F_{0}(q),y_{q}=F_{0}^{*}(q)$ . By the symmetry of $H_{i}^{*}$ , $y_{0}+y_{p}=1$ holds. So $(y_{j})$ is a symmetric $\alpha$ -normal sequence. By Corollary 3.1, we have $y_{n}=F_{0}^{*}(2n-q)$ . If $H_{i}\neq H_{i}^{*}$ , then $(l_{1},l_{2},l_{3})\neq(p,p,q)$ . Since $\alpha<\frac{1}{4}$ , By Corollary 3.1, there exists a weighted incidence matrix $B$ of $H_{i}$ which satisfies the following conditions.

(1).

When $i=1$ , for the internal loose paths $(u_{1},u_{3})$ - $P_{l_{1}}$ , $(v_{1},v_{3})$ - $P_{l_{2}}$ and $(u_{2},v_{2})$ - $P_{l_{3}}$ of $H_{1}$ , $B$ is $(F_{0}(l_{1}),F_{0}(l_{1}))$ $\alpha$ -normal, $(F_{0}(l_{2}),F_{0}(l_{2}))$ $\alpha$ -normal and $(F_{0}(m-2-2l_{1}),F_{0}(m-2-2l_{2}))$ $\alpha$ -normal. And

	$\displaystyle B(e^{\prime},u_{1})$	$\displaystyle=B(e^{\prime},u_{3})=F_{0}^{*}(l_{1}),$	$\displaystyle B(e^{\prime},u_{2})$	$\displaystyle=F_{0}^{*}(m-2-2l_{1}),$
	$\displaystyle B(e^{\prime\prime},v_{1})$	$\displaystyle=B(e^{\prime\prime},v_{3})=F_{0}^{*}(l_{2}),$	$\displaystyle B(e^{\prime\prime},v_{2})$	$\displaystyle=F_{0}^{*}(m-2-2l_{2}).$

Without loss of generality, suppose $l_{1}\leq l_{2}$ . Since $l_{1}+l_{2}+l_{3}=m-2$ , $m-2-2l_{1}=l_{2}+l_{3}-l_{1}\geq 0$ .

Since $F_{0}^{*}(x)$ is log-concave on $[-1,+\infty)$ , From $2p+q=l_{1}+l_{2}+l_{3}$ , $(l_{1},l_{2},l_{3})\neq(p,p,q)$ , we have

\prod\limits_{v\in e^{\prime}}B(v,e^{\prime})=F_{0}^{*}(l_{1})^{2}F_{0}^{*}(m-2-2l_{1})<F_{0}^{*}(p)^{2}F_{0}^{*}(q)=\alpha.

$F_{0}^{*}(l_{2})^{2}F_{0}^{*}((m-2-2l_{2}))<F_{0}^{*}(p)^{2}F_{0}^{*}(q)=\alpha$ when $m-2-2l_{2}\geq 0$ and

$F_{0}^{*}(l_{2})F_{0}^{*}(0)F_{0}^{*}(m-2-l_{2})<F_{0}^{*}(p)^{2}F_{0}^{*}(q)=\alpha$ when $m-2-2l_{2}<0$ .

By (2) of Proposition 3.1, $F_{0}^{*}(l_{2})^{2}F_{0}^{*}((m-2-2l_{2}))<F_{0}^{*}(l_{2})F_{0}^{*}(0)F_{0}^{*}(m-2-l_{2})$ . Hence, $\prod\limits_{v\in e^{\prime\prime}}B(v,e^{\prime\prime})=F_{0}^{*}(l_{2})^{2}F_{0}^{*}((m-2-2l_{2}))<\alpha$ .

(2).

When $i=2$ ,
for each $j\in\{1,2,3\}$ , the internal loose path $(u_{j},v_{j})$ - $P_{l_{j}}$ of $H_{2}$ , $B$ are $(F_{0}(l_{1}),F_{0}(l_{1}))$ $\alpha$ -normal and $B(e^{\prime},u_{j})=B(e^{\prime\prime},v_{j})=F_{0}^{*}(l_{j})$ .

Since $F_{0}^{*}(x)$ is log-concave in $[-1,+\infty)$ ,
$\prod\limits_{v\in e^{\prime}}B(v,e^{\prime})=\prod\limits_{v\in e^{\prime\prime}}B(v,e^{\prime\prime})=F_{0}^{*}(l_{1})F_{0}^{*}(l_{2})F_{0}^{*}(l_{3})<F_{0}^{*}(p)^{2}F_{0}^{*}(q)=\alpha$ .

Therefore, for $i=1,2$ , we have
$\forall v\in V(H_{i})$ , $\displaystyle\sum\limits_{e\in E(v)}B(v,e)=1;$ $\forall e\in E(H)-\{e^{\prime},e^{\prime\prime}\}$ , $\displaystyle\prod\limits_{v\in e}B(v,e)=\alpha$ .

By (1) of Lemma 2.2, $B_{i}$ is consistent with all cycles of $H_{i}$ for $i=1,2$ .

That is, $H_{i}$ is consistently $\alpha$ -supernormal, by Lemma 2.2, $\rho(H_{i})>\rho(H^{*}_{i})$ , which is a contradiction to our assumption on $H_{i}$ .

So $H_{i}=C_{i}(p,p,q)$ is the extremal hypergraph with the smallest spectral radius in $\mathscr{B}_{i}(m)$ for $i=1,2$ .∎

Theorem 5.2.

Let $p,q$ be positive integers such that $p+q=m-1$ , $|p-q|\leq 1$ . Then $C_{3}(p,q)$ is the hypergraph with the smallest spectral radius in $\mathscr{B}_{3}(m)$ .

Proof.

Let $H$ be hypergraph in $\mathscr{B}_{3}(m)$ with the smallest spectral radius. By similar arguments of proof of Lemma 5.1, $H=\widehat{H}$ . That is, $H$ is a $\Theta^{*}$ type hypergraph. Without loss of generality, suppose $H=C_{3}(l_{1},l_{2})$ and $l_{1}+l_{2}=m-1$ . Let $H^{*}=C_{3}(p,q)$ , $\alpha=\alpha(H^{*})$ . Suppose that $(y_{j})$ is the iteration sequence of $f(x)=1-\frac{\alpha}{x}$ with $y_{0}=F_{0}(q),y_{q}=F_{0}^{*}(q)$ . By the symmetry of $H^{*}$ , we have $y_{0}+y_{p}=1$ and $(y_{j})$ is a $\alpha$ -normal sequence. From Corollary 3.1, $y_{n}=F_{0}^{*}(2n-q)$ .

Since $\alpha<\frac{1}{4}$ , according to Corollary 3.1, we can build a weighted incidence matrix $B$ of $H$ such that $B$ is $(F_{0}(l_{1}),F_{0}(l_{1}))$ $\alpha$ -normal for the loose path $(u_{1},u_{2})$ - $P_{l_{1}}$ and $(F_{0}(l_{2}),F_{0}(l_{2}))$ $\alpha$ -normal for $(v_{1},v_{2})$ - $P_{l_{2}}$ ,
and $\begin{aligned} B(e^{\prime},u_{1})&=B(e^{\prime},u_{2})=F_{0}^{*}(l_{1}),&B(e^{\prime},v_{1})&=B(e^{\prime},v_{2})=F_{0}^{*}(l_{2}).\\ \end{aligned}$

Then $\forall v\in V(H)$ , $\displaystyle\sum\limits_{e\in E(v)}B(v,e)=1$ and $\forall e\in E(H)-\{e^{\prime}\}$ , $\displaystyle\prod\limits_{v\in e}B(v,e)=\alpha$ .

For $e^{\prime}$ , $\prod\limits_{v\in e^{\prime}}B(v,e^{\prime})=F_{0}^{*}(l_{1})^{2}F_{0}^{*}(l_{2})^{2}<F_{0}^{*}(p)^{2}F_{0}^{*}(q)^{2}=\alpha$ .

By (1) of Lemma 2.2, $B_{i}$ is consistent for any cycle of $H_{i}$ for $i=1,2$ .

Therefore, $H$ is consistently $\alpha$ -supernormal. According to (3) of Theorem 2.2, $\rho(H)>\rho(H^{*})$ , which is a contradiction to our assumption on $H$ .

Hence, $H=C_{3}(p,q)$ is the hypergraph with the smallest spectral radius in $\mathscr{B}_{3}(m)$ . ∎

Theorem 5.3.

Let integers $p,q$ such that $p\geq q,p+q=m-1,|p-q|\leq 1$ . Take hypergraphs $H=C_{2}(p-1,q-1,1)$ , $G=C_{3}(p,q)$ . Then $\rho(H)<\rho(G)$ .

Proof.

Set $\alpha=\alpha(G)$ . Let $(y_{j})$ be the iteration sequence of $f(x)=1-\frac{\alpha}{x}$ with $y_{0}=F_{0}(q),y_{q}=F_{0}^{*}(q)$ . By the symmetry of $G$ , $y_{0}+y_{p}=1$ . So $(y_{j})$ is a symmetric $\alpha$ -normal sequence. By Corollary 3.1, we have $y_{n}=F_{0}^{*}(2n-q)$ . Since $\alpha<\frac{1}{4}$ , by Corollary 3.1, there exists a weighted incidence matrix $B$ of $H$ such that
$B$ is $(F_{0}(l_{1}),F_{0}(l_{1}))$ $\alpha$ -normal for $(u_{1},u_{2})$ - $P_{l_{1}}$ and $(F_{0}(l_{2}),F_{0}(l_{2}))$ $\alpha$ -normal for $(v_{1},v_{2})$ - $P_{l_{2}}$ . And,

	$\displaystyle B(e^{\prime},u_{1})$	$\displaystyle=B(e^{\prime},v_{1})=F_{0}^{*}(p-1),$
	$\displaystyle B(e^{\prime},u_{2})$	$\displaystyle=B(e^{\prime},v_{2})=F_{0}^{*}(q-1),$
	$\displaystyle B(e^{\prime},u_{3})$	$\displaystyle=B(e^{\prime\prime},v_{3})=F_{0}^{*}(1),$

$\forall v\in V(H)$ , $\displaystyle\sum\limits_{e\in E(v)}B(v,e)=1,$ $\forall e\in E(H)-\{e^{\prime},e^{\prime\prime}\}$ , $\displaystyle\prod\limits_{v\in e}B(v,e)=\alpha$ .

Since $F_{0}^{*}(p)^{2}F_{0}^{*}(q)^{2}=\alpha$ , $F_{0}^{*}(x)>0$ , $F_{0}^{*}(p)F_{0}^{*}(q)=\sqrt{\alpha}=F_{0}^{*}(-1)$ .

For $e^{\prime},e^{\prime\prime}$ ,

	$\displaystyle\prod\limits_{v\in e^{\prime}}B(v,e^{\prime})=\prod\limits_{v\in e^{\prime\prime}}B(v,e^{\prime\prime})=$	$\displaystyle F_{0}^{}(p-1)F_{0}^{}(q-1)F_{0}^{*}(1)$
	$\displaystyle>$	$\displaystyle F_{0}^{}(p)F_{0}^{}(q)F_{0}^{*}(-1)=\alpha.$

By (2) of Theorem 2.2, $H$ is $\alpha$ -subnormal. $\rho(H)<\rho(G)$ holds. ∎

From Lemmas 5.1, 5.2 and Theorems 5.1, 5.2, 5.3, we derive our main result.

Theorem 5.4.

Let $H_{1}$ and $H_{2}$ be the hypergraph with the smallest spectral radius in $\mathscr{B}_{1}(m),\mathscr{B}_{2}(m)$ , respectively. Then

(1).

$\rho(H_{1})=\rho(H_{2})$ ,
(2).

$H_{1},H_{2}$ are the hypergraphs with the smallest spectral radius in $\mathscr{B}(m)$ .

According to those results obtained, we can compute the values of spectral radii of $k$ -graphs with the smallest spectral radius.

Let $\rho$ be the smallest spectral radius of bicyclic $k$ -graph with size $m$ and $q=\lfloor\frac{m-2}{3}\rfloor$ . Suppose

F(\theta)=\begin{cases}F_{0}^{*}(q)^{2}F_{0}^{*}(q+1)&\text{for $m\equiv 0\pmod{3}$ },\\ F_{0}^{*}(q)F_{0}^{*}(q+1)^{2}&\text{for $m\equiv 1\pmod{3}$ },\\ F_{0}^{*}(q)^{3}&\text{for $m\equiv 2\pmod{3}$ }.\\ \end{cases}

Let $\theta_{0}$ be the unique positive root of equation

F(\theta)-\frac{1}{4}\operatorname{sech}(\theta)^{2}=0.

Then $\rho=(2\cosh(\theta_{0}))^{\frac{2}{k}}$ .

As a example, we take $H$ to be a $k$ -graph with the smallest spectral radius in $\mathscr{B}(14)$ for $k=3$ . Let $\alpha=\alpha(H)$ and $\theta_{0}=\operatorname{arcosh}(\frac{1}{2}\alpha^{-\frac{1}{2}})$ . Then $\theta_{0}$ is the positive root of the following equation

(1+\tanh(\theta)\tanh(2\theta))^{3}-2\operatorname{sech}^{2}(\theta)=0.

By direct calculation, we have $\theta_{0}\approx 0.35581$ and $\alpha(H)\approx 0.22084$ . Hence, $\rho(H)=(2\cosh(\theta_{0}))^{\frac{2}{3}}\approx 1.654396$ .

References

[1] C. Berge, Graphs and hypergraphs, North-Holland Publishing Co., New York, 1973.
[2] Y.-Z. Fan, Y.-Y. Tan, X.-X. Peng, A.-H. Liu, Maximizing spectral radii of uniform hypergraphs with few edges, Discuss. Math. Graph Theory 36 (4) (2016) 845–856.
[3] H. Li, J.-Y. Shao, L. Qi, The extremal spectral radii of $k$ -uniform supertrees, Journal of Combinatorial Optimization 32 (3) (2016) 741–764.
[4] P. Xiao, L. Wang, Y. Lu, The maximum spectral radii of uniform supertrees with given degree sequences, Linear Algebra and its Applications 523 (2017) 33–45.
[5] X. Yuan, J. Shao, H. Shan, Ordering of some uniform supertrees with larger spectral radii, Linear Algebra and Its Applications 495 (2016) 206–222.
[6] L. Lu, S. Man, Connected hypergraphs with small spectral radius, Linear Algebra and Its Applications 509 (2016) 206–227.
[7] C. Ouyang, L. Qi, X. Yuan, The first few unicyclic and bicyclic hypergraphs with largest spectral radii, Linear Algebra Appl. 527 (2017) 141–162.
[8] J. Zhang, J. Li, H. Guo, Uniform hypergraphs with the first two smallest spectral radii, Linear Algebra and its Applications 594 (2020) 71–80.
[9] L.-H. Lim, Singular values and eigenvalues of tensors: a variational approach, in: Computational Advances in Multi-Sensor Adaptive Processing, 2005 1st IEEE International Workshop on, IEEE, 2005, pp. 129–132.
[10] L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (6) (2005) 1302–1324.
[11] J. Cooper, A. Dutle, Spectra of uniform hypergraphs, Linear Algebra and its applications 436 (9) (2012) 3268–3292.
[12] M.-u.-I. Khan, Y.-Z. Fan, On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs, Linear Algebra Appl. 480 (2015) 93–106.
[13] A. F. Beardon, Iteration of rational functions: Complex analytic dynamical systems, Vol. 132, Springer Science & Business Media, 2000.
[14] L. Brand, A sequence defined by a difference equation, The American Mathematical Monthly 62 (7) (1955) 489–492.
[15] A. W. Marshall, I. Olkin, B. C. Arnold, Inequalities: theory of majorization and its applications, Vol. 143, Springer, 1979.
[16] F. Wang, H. Shan, Z. Wang, On some properties of the $\alpha$ -spectral radius of the k-uniform hypergraph, Linear Algebra and its Applications 589 (2020) 62–79.

The smallest spectral radius of bicyclic uniform hypergraphs with a given size

Abstract

1 Introduction

Definition 1.1.

2 Preliminaries

Definition 2.1 ([11]).

Theorem 2.1.

Definition 2.2.

Definition 2.3.

Definition 2.4.

Theorem 2.2.

Lemma 2.1.

Definition 2.5.

Lemma 2.2.

Proof.

3 On a kind of sequence obtained by iteration of Möbius transform

Lemma 3.1.

Proof.

Theorem 3.1.

Proof.

Corollary 3.1.

Proof.

Definition 3.1.

Theorem 3.2.

Theorem 3.3.

Proof.

Proposition 3.1.

Proof.

4 The effect on the spectral radii of uniform hypergraphs by some graph operations

Definition 4.1 (Edge moving operation [16]).

Lemma 4.1.

Corollary 4.1.

Proof.

Definition 4.2 (vertex-splitting operation).

Lemma 4.2.

Proof.

Proposition 4.1.

Proof.

Claim 1.

Proof.

Lemma 4.3.

Proof.

Theorem 4.1.

Proof.

Definition 4.3 (Vertex-releasing operation).

Theorem 4.2.

Proof.

Theorem 4.3.

Proof.

Corollary 4.2.

5 Extremal hypergraphs in ℬ​(m)\mathscr{B}(m) with the smallest spectral radius

Proposition 5.1.

Proof.

Lemma 5.1.

Proof.

Lemma 5.2.

Proof.

Theorem 5.1.

Proof.

Theorem 5.2.

Proof.

Theorem 5.3.

Proof.

Theorem 5.4.

References

5 Extremal hypergraphs in $\mathscr{B}(m)$ with the smallest spectral radius