Huiqiu Lin

The largest eigenvalue of $C_{4}^{-}$ -free signed graphs

Yongang Wang, Huiqiu Lin

Let $C_{k}^{-}$ be the set of all negative $C_{k}$ . For odd cycle, Wang, Hou and Li [29] gave a spectral condition for the existence of negative $C_{3}$ in unbalanced signed…

Maximizing the Steklov eigenvalues on trees with a diameter constraint

Jiangdong Ai, Huiqiu Lin, Yongtang Shi

We study the first nonzero Steklov eigenvalue $I^»_{2} (T, I^´ I^c ◯)$ of the Dirichlet-to-Neumann operator on a finite tree $T$ with leaf boundary $I^´ I^c ◯$ , under a constraint on the diameter…

Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs

Mingqing Zhai, Huiqiu Lin, Jinlong Shu

Nikiforov [Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 179--189] showed that if $G$ is $K_{r + 1}$ -free then the spectral radius $Ï(G)\leq\sqrt{…

l-connectivity, l-edge-connectivity and spectral radius of graphs

Dandan Fan, Xiaofeng Gu, Huiqiu Lin

Let G be a connected graph. The toughness of G is defined as t(G)=min{\frac{|S|}{c(G-S)}}, in which the minimum is taken over all proper subsets S\subset V(G) such that c(G-S)\geq…

A Complete Solution to the CvetkoviÄ-Rowlinson Conjecture

Huiqiu Lin, Bo Ning

In 1990, CvetkoviÄ and Rowlinson [The largest eigenvalue of a graph: a survey, Linear Multilinear Algebra 28(1-2) (1990), 3--33] conjectured that among all outerplanar graphs on $…

math.CO2017

Graphs determined by their $A_{I^} \pm$ -spectra

Huiqiu Lin, Xiaogang Liu, Jie Xue

Let $G$ be a graph with $n$ vertices, and let $A (G)$ and $D (G)$ denote respectively the adjacency matrix and the degree matrix of $G$ . Define $A_{I^} \pm (G) = I^\pm D (G) + (1 - I^\pm) A (G)$ for an…

Maximize the Steklov eigenvalue of trees

Huiqiu Lin, Da Zhao

We study the maximal Steklov eigenvalues of trees with given number of boundary vertices and total number of vertices. Trees can be regarded as discrete analogue of Hadamard manifo…

Edge-spectral supersaturation for tripartite color-critical graphs

Longfei Fang, Huiqiu Lin, Mingqing Zhai

We study edge-spectral supersaturation for two families of color-critical graphs with chromatic number three. For an integer $r \geq 1$ , we define the spectral threshold \[ g_r(m):=…

Spectral radius and $[a, b]$ -factors in graphs

Dandan Fan, Huiqiu Lin, Hongliang Lu

An $[a, b]$ -factor of a graph $G$ is a spanning subgraph $H$ such that $a \leq d_{H} (v) \leq b$ for each $v \in V (G)$ . In this paper, we provide spectral conditions for the existence o…

Spectral extremal problem on $t$ copies of $ℓ$ -cycle

Longfei Fang, Mingqing Zhai, Huiqiu Lin

Denote by $t C_{ℓ}$ the disjoint union of $t$ cycles of length $ℓ$ . Let $e x (n, F)$ and $s p e x (n, F)$ be the maximum size and spectral radius over all $n$ -vertex $F$ -free graphs, re…

A Faber--Krahn inequality for trees

Huiqiu Lin, Lianping Liu, Zhe You

The well-known Faber-Krahn theorem states that the ball has the lowest first Dirichlet eigenvalue among all domains of the same volume in $R^{n}$ . Leydold (Geom. Funct. Anal…

Spectral radius and edge-disjoint spanning trees

Dandan Fan, Xiaofeng Gu, Huiqiu Lin

The spanning tree packing number of a graph $G$ , denoted by $I ¨ (G)$ , is the maximum number of edge-disjoint spanning trees contained in $G$ . The study of $I ¨ (G)$ is one of the clas…

Spectral radius and (globally) rigidity of graphs in $R^{2}$

Dandan Fan, Xueyi Huang, Huiqiu Lin

Over the past half century, the rigidity of graphs in $R^{2}$ has aroused a great deal of interest. LovÃ¡sz and Yemini (1982) proved that every $6$ -connected graph is rigid in $R^{2}$ .…

math.CO2019

Signless Laplacian eigenvalue problems of Nordhaus-Gaddum type

Xueyi Huang, Huiqiu Lin

Let $G$ be a graph of order $n$ , and let $q_{1} (G) \geq q_{2} (G) \geq \dots \geq q_{n} (G)$ denote the signless Laplacian eigenvalues of $G$ . Ashraf and Tayfeh-Rezaie [Electron. J. Combin. 2…

Spectral extremal results for triangle-free graphs with chromatic number at least four

Yinfen Zhu, Huiqiu Lin

A graph is called $F$ -free if it does not contain a copy of $F$ . Let $G (r, s)$ denote a $K_{r + 1}$ -free graph of order $n$ with chromatic number at least $s$ that maximizes the spect…

math.CO2019

On $k$ -idempotent 0-1 matrices

Zejun Huang, Huiqiu Lin

Let $k \geq 2$ be an integer. If a square 0-1 matrix $A$ satisfies $A^{k} = A$ , then $A$ is said to be $k$ -idempotent. In this paper, we give a characterization of $k$ -idempotent 0-1 mat…

Spectral extremal graphs on closed surfaces of fixed Euler genus

Mingqing Zhai, Longfei Fang, Huiqiu Lin

Graph theory on surfaces extends classical graph structures to topological surfaces, providing a theoretical foundation for characterizing the embedding properties of complex netwo…

Spectral extremal results on edge blow-up of graphs

Longfei Fang, Huiqiu Lin

Let $ex (n, F)$ and $spex (n, F)$ be the maximum size and maximum spectral radius of an $F$ -free graph of order $n$ , respectively. The value $spex (n, F)$ is called the…

Spectral extremal results on trees

Longfei Fang, Huiqiu Lin, Jinlong Shu +1

Let $spex (n, F)$ be the maximum spectral radius over all $F$ -free graphs of order $n$ , and $SPEX (n, F)$ be the family of $F$ -free graphs of order $n$ with spectral radius…

quant-ph2026

Zero transfer on mixed graphs

Xingkun Song, Huiqiu Lin

In this paper, we investigate zero transfer on mixed graphs. Zero transfer is a quantum walk phenomenon in which the transition amplitude between two vertices is identically zero f…

Spectral radius, edge-disjoint cycles and cycles of the same length

Huiqiu Lin, Mingqing Zhai, Yanhua Zhao

In this paper, we give spectral conditions to guarantee the existence of two edge disjoint cycles and two cycles of the same length. These two results can be seen as spectral analo…

State transfer on integral mixed circulant graphs

Xing-Kun Song, Huiqiu Lin

A mixed circulant graph is called integral if all eigenvalues of its Hermitian adjacency matrix are integers. The main purpose of this paper is to investigate the existence of perf…

A strengthening of the spectral chromatic critical edge theorem: books and theta graphs

Mingqing Zhai, Huiqiu Lin

The chromatic critical edge theorem of Simonovits states that for a given color critical graph $H$ with $I ¨ (H) = k + 1$ , there exists an $n_{0} (H)$ such that the TurÃ¡n graph $T_{n, k}$ i…

A unified approach to the spectral radius, connectivity and edge-connectivity of graphs

Yu Wang, Dan Li, Huiqiu Lin

For two integers $r \geq 2$ and $h \geq 0$ , the \emph{ $h$ -extra $r$ -component connectivity} $I^º_{r}^{h} (G)$ of a graph $G$ is defined to be the minimum size of a subset of vertices whose…

The spanning $k$ -trees, perfect matchings and spectral radius of graphs

Dandan Fan, Sergey Goryainov, Xueyi Huang +1

A $k$ -tree is a spanning tree in which every vertex has degree at most $k$ . In this paper, we provide a sufficient condition for the existence of a $k$ -tree in a connected graph wi…

math.CO2016

The distance spectra of the derangement graphs

Yunnan Li, Huiqiu Lin

In this paper, we consider the distance spectra of the derangement graphs. First we give a constructive proof that the connected derangement graphs are of diameter 2. Then we obtai…

More on spectral supersaturation for the bowtie

Longfei Fang, Yongtao Li, Huiqiu Lin

A central topic in extremal graph theory is the supersaturation problem, which studies the minimum number of copies of a fixed substructure that must appear in any graph with more…

Spectral radius, toughness and $k$ -factor of graphs

Yuanyuan Chen, Huiqiu Lin, Shucheng Li

A $k$ -regular spanning subgraph of $G$ is called a $k$ -factor. Fan, Lin and Lu [European J. Combin. 110 (2023) 103701] presented a tight sufficient condition in terms of the spectr…

Counting color-critical subgraphs under Nikiforov's condition

Longfei Fang, Huiqiu Lin, Mingqing Zhai

For a graph $G$ with $m$ edges, let $I ¨ (G)$ be its spectral radius, and let $N_{F} (G)$ denote the number of copies of $F$ in $G$ . Nikiforov [Combin. Probab.\,Comput., 2002] proved th…

Proof of Lew's conjecture on the spectral gaps of simplicial complexes

Xiongfeng Zhan, Xueyi Huang, Huiqiu Lin

As a generalization of graph Laplacians to higher dimensions, the combinatorial Laplacians of simplicial complexes have garnered increasing attention. Let $X$ be a simplicial compl…

Toughness and spectral radius in graphs

Yuanyuan Chen, Dandan Fan, Huiqiu Lin

The Brouwer's toughness conjecture states that every $d$ -regular connected graph always has $t (G) > \frac{d}{I ^} » - 1$ where $I^»$ is the second largest absolute eigenvalue of the adjacenc…

Perfect matching and distance spectral radius in graphs and bipartite graphs

Yuke Zhang, Huiqiu Lin

A perfect matching in a graph $G$ is a set of nonadjacent edges covering every vertex of $G$ . Motivated by recent progress on the relations between the eigenvalues and the matching…

math.CO2018

On the sum of $k$ -th largest distance eigenvalues of graphs

Huiqiu Lin

For a connected graph $G$ with order $n$ and an integer $k \geq 1$ , we denote by $S_{k} (D (G)) = I^»_{1} (D (G)) + \dots + I^»_{k} (D (G))$ the sum of $k$ largest distance eigenvalues of $G$ . In th…

math.CO2015

Remoteness and distance eigenvalues of a graph

Huiqiu Lin, Kinkar Ch. Das, Baoyindureng Wu

Let $G$ be a connected graph of order $n$ with diameter $d$ . Remoteness $I ¨ $ of $G$ is the maximum average distance from a vertex to all others and $\partial_1\geq\cdots\geq \parti…

Graphs with positive Lin-Lu-Yau curvature without quadrilaterals

Huiqiu Lin, Zhe You

The definition of Ricci curvature on graphs was given in Lin-Lu-Yau, Tohoku Math., 2011, which is a variation of Ollivier, J. Funct. Math., 2009. Recently, a powerful limit-free fo…

Spectral conditions for $k$ -extendability and $k$ -factors of bipartite graphs

Dandan Fan, Huiqiu Lin

Let $G$ be a connected graph. If $G$ contains a matching of size $k$ , and every matching of size $k$ is contained in a perfect matching of $G$ , then $G$ is said to be \emph{ $k$ -ext…

Spectral extrema of $K_{s, t}$ -minor free graphs--On a conjecture of M. Tait

Mingqing Zhai, Huiqiu Lin

Minors play an important role in extremal graph theory and spectral extremal graph theory. Tait [The Colin de VerdiÃ¨re parameter, excluded minors, and the spectral radius, J. Comb…

Eigenvalues of signed graphs

Dan Li, Huiqiu Lin, Jixiang Meng

Signed graphs have their edges labeled either as positive or negative. $I ¨ (M)$ denote the $M$ -spectral radius of $I^£$ , where $M = M (I^£)$ is a real symmetric graph matrix of $I^£$ . Obv…

On the spectral extremal problem of planar graphs

Xiaolong Wang, Xueyi Huang, Huiqiu Lin

The spectral extremal problem of planar graphs has aroused a lot of interest over the past three decades. In 1991, Boots and Royle [Geogr. Anal. 23(3) (1991) 276--282] (and Cao and…

The spectral TurÃ¡n problem: Characterizing spectral-consistent graphs

Longfei Fang, Sergey Goryainov, Denis Krotov +2

Let $EX (n, H)$ and $SPEX (n, H)$ denote the families of $n$ -vertex $H$ -free graphs with the maximum size and the maximum spectral radius, respectively. A graph $H$ is said…

Spectral supersaturation for color-critical graphs

Longfei Fang, Yongtao Li, Huiqiu Lin +1

A graph is color-critical if it contains an edge whose deletion reduces its chromatic number. This class of graphs, including cliques and odd cycles, plays a central role in extrem…

The existence of biregular spanning subgraphs in bipartite graphs via spectral radius

Dandan Fan, Xiaofeng Gu, Huiqiu Lin

Biregular bipartite graphs have been proven to have similar edge distributions to random bipartite graphs and thus have nice pseudorandomness and expansion properties. Thus it is q…

math.CO2018

A note on the $A_{I^} \pm$ -spectral radius of graphs

Huiqiu Lin, Xing Huang, Jie Xue

Let $G$ be a graph with adjacency matrix $A (G)$ and let $D (G)$ be the diagonal matrix of the degrees of $G$ . For any real $I^\pm \in [0, 1]$ , Nikiforov [Merging the $A$ - and $Q$ -spectra…

Krahn--SzegÅ type inequalities and nodal domain methods on graphs

Huiqiu Lin, Lianping Liu, Xilong Yin +1

We study discrete analogues of classical spectral geometric inequalities and extremal eigenvalue problems on graphs. The classical Krahn--SzegÅ inequality states that, among bound…

Graphs with nonnegative Bakry-Ãmery curvature without Quadrilateral

Huiqiu Lin, Zhe You

The definition of Ricci curvature on graphs in Bakry-Ãmery's sense based on curvature dimension condition was introduced by Lin and Yau [\emph{Math. Res. Lett.}, 2010]. Hua and Li…

Eigenvalues and factors: a survey

Dandan Fan, Huiqiu Lin, Hongliang Lu +1

A factor of a graph is a spanning subgraph satisfying some given conditions. An earlier survey of factors can be traced back to the Akiyama and Kano [J. Graph Theory, 1985, 9: 1-42…

math.CO2017

More results on the distance (signless) Laplacian eigenvalues of graphs

Jie Xue, Huiqiu Lin, Kinkar Ch. Das +1

Let $G$ be a connected graph with vertex set $V (G)$ and edge set $E (G)$ . Let $T r (G)$ be the diagonal matrix of vertex transmissions of $G$ and $D (G)$ be the distance matrix of $G$ .…

math.CO2020

On the $A_{I^} \pm$ -spectra of graphs

Huiqiu Lin, Jie Xue, Jinlong Shu

Let $G$ be a graph with adjacency matrix $A (G)$ and let $D (G)$ be the diagonal matrix of the degrees of $G$ . For any real $I^\pm \in [0, 1]$ , Nikiforov \cite{VN1} defined the matrix $A_…

Extremal spectral results of planar graphs without vertex-disjoint cycles

Longfei Fang, Huiqiu Lin, Yongtang Shi

Given a planar graph family $F$ , let $ex_{P} (n, F)$ and $spex_{P} (n, F)$ be the maximum size and maximum spectral radius…

Halin graphs with positive Lin-Lu-Yau curvature

Kaizhe Chen, Huiqiu Lin, Shiping Liu +1

Halin graphs constitute an interesting class of planar and polyhedral graphs. A generalized Halin graph is obtained by connecting all leaves of a planar embedding of a tree via a c…

Non-bipartite graphs without theta subgraphs

Longfei Fang, Huiqiu Lin

Fix a color-critical graph $H$ with $I ¨ (H) = r + 1 \geq 3$ . Simonovits' chromatic critical edge theorem and Nikiforov's spectral chromatic critical edge theorem imply that $T_{n, r}$ is…

The first Steklov eigenvalue of planar graphs and beyond

Huiqiu Lin, Da Zhao

The Steklov eigenvalue problem was introduced over a century ago, and its discrete form attracted interest recently. Let $D$ and $I^´ I^c ◯$ be the maximum vertex degree and the set of…

The EKR-module property of pseudo-Paley graphs of square order

Shamil Asgarli, Sergey Goryainov, Huiqiu Lin +1

We prove that a family of pseudo-Paley graphs of square order obtained from unions of cyclotomic classes satisfies the ErdÅs-Ko-Rado (EKR) module property, in a sense that the cha…

A local spectral condition for perfect matchings in 3-graphs

Huiqiu Lin, Hongliang Lu, Feihong Yuan +1

Let $I^^{3}$ be a constant such that $0 < I^^{3} < 1$ , and let $n$ be a sufficiently large integer. Consider a $3$ -uniform hypergraph $H$ on $n$ vertices. In 2013, KÃ¼hn, Osthus, and Treglo…

math.CO2020

Eigenvalues and triangles in graphs

Huiqiu Lin, Bo Ning, Baoyindureng Wu

BollobÃ¡s and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r + 1}$ -free graph on at least $r + 1$ vertices and $m$ edges, then $…

math.SP2026

Minimally $(k, k)$ -edge-connected graphs via spectral radius

Yu Wang, Dan Li, Huiqiu Lin

For $l > 1$ , the $l$ -edge-connectivity $I^º_{l}^{'} (G)$ of a connected graph $G$ is defined as the minimum number of edges whose removal leaves a graph with at least $l$ components. A gr…

On balanced characteristic functions of canonical cliques in Paley graphs of square order

Sergey Goryainov, Huiqiu Lin

In this paper we prove that balanced characteristic functions of canonical cliques in a Paley graph of square order $P (q^{2})$ span the $\frac{- 1 + q}{2}$ -eigenspace of the graph. This…

Bipartite graphs, random graphs, and Lin--Lu--Yau curvature

Huiqiu Lin, Zhe You, Da Zhao

Let $G = (X, Y; E)$ be a bipartite graph with parts $X$ and $Y$ where $∣ X ∣ = m$ and $∣ Y ∣ = n$ . We show that every bipartite graph with more than $mn - D (m, n)$ edges has positive Lin--L…

math.SP2025

A note on the spectral radius and $[a, b]$ -factor of graphs

Dandan Fan, Huiqiu Lin, Yinfen Zhu

The investigation of eigenvalue conditions for the existence of an $[a, b]$ -factor originates in the work of Brouwer and Haemers (2005) on perfect matchings. In the decades since, s…

Extremal eigenvalues with respect to graph minors

Mingqing Zhai, Longfei Fang, Huiqiu Lin

Let $s p e x (n, H_{min or})$ denote the maximum spectral radius of $n$ -vertex $H$ -minor free graphs. The problem on determining this extremal value can be dated back to the early 1990s.…

On the TurÃ¡n number of odd-ballooning of $3$ -chromatic graphs

Longfei Fang, Xueyi Huang, Huiqiu Lin +1

Given a graph $F$ , the TurÃ¡n number $ex (n, F)$ is the maximum number of edges in any $n$ -vertex $F$ -free graph. The odd-ballooning of $F$ , denoted by $F^{o}$ , is a graph obta…

Upper bounds of Steklov eigenvalues on graphs

Huiqiu Lin, Lianping Liu, Zhe You +1

Let $I^$ and $B$ be the maximum vertex degree and a subset of vertices in a graph $G$ respectively. In this paper, we study the first (non-trivial) Steklov eigenvalue $I ¨ _{2}$ of $G$ …

math.CO2020

The maximum spectral radius of wheel-free graphs

Yanhua Zhao, Xueyi Huang, Huiqiu Lin

A wheel graph is a graph formed by connecting a single vertex to all vertices of a cycle. A graph is called wheel-free if it does not contain any wheel graph as a subgraph. In 2010…

Graphs with three distinct distance eigenvalues

Yuke Zhang, Huiqiu Lin

In this paper, some special distance spectral properties of graphs are considered. Concretely, we recursively construct an infinite family of trees with distance eigenvalue $- 1$ , a…

Long cycles and spectral radii in planar graphs

Ping Xu, Huiqiu Lin, Longfei Fang

There is a rich history of studying the existence of cycles in planar graphs. The famous Tutte theorem on the Hamilton cycle states that every 4-connected planar graph contains a H…

Toughness, hamiltonicity and spectral radius in graphs

Dandan Fan, Huiqiu Lin, Hongliang Lu

The study of the existence of hamiltonian cycles in a graph is a classic problem in graph theory. By incorporating toughness and spectral conditions, we can consider ChvÃ¡tal's con…

math.CO2013

Spectral conditions for the existence of specified paths and cycles in graphs

Mingqing Zhai, Huiqiu Lin, Shicai Gong

Let $G$ be a graph with $n$ vertices and $I^»_{n} (G)$ be the least eigenvalue of its adjacency matrix of $G$ . In this paper, we give sharp bounds on the least eigenvalue of graphs wit…

Estimates of the first Dirichlet eigenvalue of graphs

Huiqiu Lin, Lianping Liu, Zhe You +1

Inspired by the Li--Yau eigenvalue-diameter estimates, we investigate lower bounds for the first Dirichlet eigenvalue in terms of the diameter (or inscribed radius) of a graph. Let…

Spectral expansion properties of pseudorandom bipartite graphs

Dandan Fan, Xiaofeng Gu, Huiqiu Lin

An $(a, b)$ -biregular bipartite graph is a bipartite graph with bipartition $(X, Y)$ such that each vertex in $X$ has degree $a$ and each vertex in $Y$ has degree $b$ . By the bipart…