BZPEER

preprint2026arXiv

More on spectral supersaturation for the bowtie

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 edges than the corresponding Turán number. Significant works due to Erdős, Rademacher, Lovász and Simonovits investigated the supersaturation problem for the triangle. Moreover, Kang, Makai and Pikhurko studied the case for the bowtie, which consists of two triangles sharing a vertex. Building upon the pivotal results established by Bollobás, Nikiforov, Ning and Zhai on counting triangles via the spectral radius, we study in this paper the spectral supersaturation problem for the bowtie. Let $λ(G)$ be the spectral radius of a graph $G$ , and let $K_{\lceil \frac{n}{2}\rceil, \lfloor \frac{n}{2}\rfloor}^q$ be the graph obtained from Turán graph $T_{n,2}$ by adding $q$ pairwise disjoint edges to the partite set of size $\lceil \frac{n}{2}\rceil$ . Firstly, we prove that there exists an absolute constant $δ>0$ such that if $n$ is sufficiently large, $2\le q \le δ\sqrt{n}$ , and $G$ is an $n$ -vertex graph with $λ(G)\ge λ(K_{\lceil \frac{n}{2}\rceil, \lfloor \frac{n}{2}\rfloor}^q)$ , then $G$ contains at least ${q\choose 2}\lfloor \frac{n}{2}\rfloor$ bowties, and $K_{\lceil \frac{n}{2}\rceil, \lfloor \frac{n}{2}\rfloor}^q$ is the unique spectral extremal graph. This solves an open problem proposed by Li, Feng and Peng. Secondly, we show that a graph $G$ whose spectral radius exceeds that of the spectral extremal graph for the bowtie must contain at least $\lfloor \frac{n-1}{2}\rfloor$ bowties. This sharp bound reveals a distinct phenomenon from the edge-supersaturation case, which guarantees at least $\lfloor \frac{n}{2}\rfloor$ bowties.

preprint2022arXiv

Eigenvalues of signed graphs

Signed graphs have their edges labeled either as positive or negative. $ρ(M)$ denote the $M$ -spectral radius of $Σ$ , where $M=M(Σ)$ is a real symmetric graph matrix of $Σ$ . Obviously, $ρ(M)=\mbox{max}\{λ_1(M),-λ_n(M)\}$. Let $A(Σ)$ be the adjacency matrix of $Σ$ and $(K_n,H^-)$ be a signed complete graph whose negative edges induce a subgraph $H$ . In this paper, we first focus on a central problem in spectral extremal graph theory as follows: Which signed graph with maximum $ρ(A(Σ))$ among $(K_n,T^-)$ where $T$ is a spanning tree? To answer the problem, we characterize the extremal signed graph with maximum $λ_1(A(Σ))$ and minimum $λ_n(A(Σ))$ among $(K_n,T^-)$ , respectively. Another interesting graph matrix of a signed graph is distance matrix, i.e. $D(Σ)$ which was defined by Hameed, Shijin, Soorya, Germina and Zaslavsky [8]. Note that $A(Σ)=D(Σ)$ when $Σ\in (K_n,T^-)$ . In this paper, we give upper bounds on the least distance eigenvalue of a signed graph $Σ$ with diameter at least 2. This result implies a result proved by Lin [11] was originally conjectured by Aouchiche and Hansen [1].

preprint2022arXiv

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

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$ . Jackson and Jordán (2005) provided a similar vertex-connectivity condition for the globally rigidity of graphs in $R^2$ . These results imply that a graph $G$ with algebraic connectivity $μ(G)>5$ is (globally) rigid in $R^2$ . Cioabă, Dewar and Gu (2021) improved this bound, and proved that a graph $G$ with minimum degree $δ\geq 6$ is rigid in $R^2$ if $μ(G)>2+\frac{1}{δ-1}$ , and is globally rigid in $R^2$ if $μ(G)>2+\frac{2}{δ-1}$ . In this paper, we study the (globally) rigidity of graphs in $R^2$ from the viewpoint of adjacency eigenvalues. Specifically, we provide sufficient conditions for a 2-connected (resp. 3-connected) graph with given minimum degree to be rigid (resp. globally rigid) in terms of the spectral radius. Furthermore, we determine the unique graph attaining the maximum spectral radius among all minimally rigid graphs of order $n$ .

preprint2022arXiv

Spectral radius and edge-disjoint spanning trees

The spanning tree packing number of a graph $G$ , denoted by $τ(G)$ , is the maximum number of edge-disjoint spanning trees contained in $G$ . The study of $τ(G)$ is one of the classic problems in graph theory. Cioabă and Wong initiated to investigate $τ(G)$ from spectral perspectives in 2012 and since then, $τ(G)$ has been well studied using the second largest eigenvalue of the adjacency matrix in the past decade. In this paper, we further extend the results in terms of the number of edges and the spectral radius, respectively; and prove tight sufficient conditions to guarantee $τ(G)\geq k$ with extremal graphs characterized. Moreover, we confirm a conjecture of Ning, Lu and Wang on characterizing graphs with the maximum spectral radius among all graphs with a given order as well as fixed minimum degree and fixed edge connectivity. Our results have important applications in rigidity and nowhere-zero flows. We conclude with some open problems in the end.

preprint2022arXiv

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

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 characteristic vector of each maximum clique is a linear combination of characteristic vectors of canonical cliques. This extends the EKR-module property of Paley graphs of square order and solves a problem proposed by Godsil and Meagher. Different from previous works, which heavily rely on tools from number theory, our approach is purely combinatorial in nature. The main strategy is to view these graphs as block graphs of orthogonal arrays, which is of independent interest.

preprint2022arXiv

Toughness, hamiltonicity and spectral radius in graphs

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 conjecture from another perspective: what is the spectral condition to guarantee the existence of a hamiltonian cycle among $t$ -tough graphs? We first give the answer to $1$ -tough graphs, i.e. if $ρ(G)\geqρ(M_{n})$ , then $G$ contains a hamiltonian cycle, unless $G\cong M_{n}$ , where $M_{n}=K_{1}\nabla K_{n-4}^{+3}$ and $K_{n-4}^{+3}$ is the graph obtained from $3K_{1}\cup K_{n-4}$ by adding three independent edges between $3K_{1}$ and $K_{n-4}$ . The Brouwer's toughness theorem states that every $d$ -regular connected graph always has $t(G)>\frac{d}λ-1$ where $λ$ is the second largest absolute eigenvalue of the adjacency matrix. In this paper, we extend the result in terms of its spectral radius, i.e. we provide a spectral condition for a graph to be 1-tough with minimum degree $δ$ and to be $t$ -tough, respectively.

preprint2021arXiv

A Complete Solution to the Cvetković-Rowlinson Conjecture

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 $n$ vertices, $K_1\vee P_{n-1}$ attains the maximum spectral radius. In 2017, Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory, Ser. B 126 (2017) 137-161] confirmed the conjecture for sufficiently large values of $n$ . In this article, we show the conjecture is true for all $n\geq2$ except for $n=6$ .

preprint2021arXiv

Perfect matching and distance spectral radius in graphs and bipartite graphs

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 number of a graph, in this paper, we aim to present a distance spectral radius condition to guarantee the existence of a perfect matching. Let $G$ be an $n$ -vertex connected graph where $n$ is even and $λ_{1}(D(G))$ be the distance spectral radius of $G$ . Then the following statements are true. \noindent $\rm{I)}$ If $4\le n\le10$ and ${λ}_{1} (D\left(G\right))\le {λ}_{1} (D(S_{n,{\frac{n}{2}}-1}))$ , then $G$ contains a perfect matching unless $G\cong S_{n,{\frac{n}{2}-1}}$ where $S_{n,{\frac{n}{2}-1}}\cong K_{{\frac{n}{2}-1}}\vee ({\frac{n}{2}+1})K_1$ . \noindent $\rm{II)}$ If $n\ge 12$ and ${λ}_{1} (D\left(G\right))\le {λ}_{1} (D(G^*))$ , then $G$ contains a perfect matching unless $G\cong G^*$ where $G^*\cong K_1\vee (K_{n-3}\cup2K_1)$ . Moreover, if $G$ is a connected $2n$ -vertex balanced bipartite graph with $λ_{1}(D(G))\le λ_{1}(D(B_{n-1,n-2}))$ , then $G$ contains a perfect matching, unless $G\cong B_{n-1,n-2}$ where $B_{n-1,n-2}$ is obtained from $K_{n,n-2}$ by attaching two pendent vertices to a vertex in the $n$ -vertex part.

preprint2021arXiv

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

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{2m(1-1/r)}$ , which implies that $G$ contains $C_3$ if $ρ(G)>\sqrt{m}$ . In this paper, we follow this direction on determining which subgraphs will be contained in $G$ if $ρ(G)> f(m)$ , where $f(m)\sim\sqrt{m}$ as $m\rightarrow \infty$ . We first show that if $ρ(G)\geq \sqrt{m}$ , then $G$ contains $K_{2,r+1}$ unless $G$ is a star; and $G$ contains either $C_3^+$ or $C_4^+$ unless $G$ is a complete bipartite graph, where $C_t^+$ denotes the graph obtained from $C_t$ and $C_3$ by identifying an edge. Secondly, we prove that if $ρ(G)\geq{\frac12+\sqrt{m-\frac34}}$ , then $G$ contains pentagon and hexagon unless $G$ is a book; and if $ρ(G)>{\frac12(k-\frac12)+\sqrt{m+\frac14(k-\frac12)^2}}$ , then $G$ contains $C_t$ for every $t\leq 2k+2$ . In the end, some related conjectures are provided for further research.

preprint2020arXiv

On the $A_α$ -spectra of graphs

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 $α\in [0,1]$ , Nikiforov \cite{VN1} defined the matrix $A_α(G)$ as $A_α(G)=αD(G)+(1-α)A(G).$ In this paper, we give some results on the eigenvalues of $A_α(G)$ with $α>1/2$ . In particular, we show that for each $e\notin E(G)$ , $λ_i(A_α(G+e))\geqλ_i(A_α(G))$ . By utilizing the result, we prove have $λ_k(A_α(G))\leqαn-1$ for $2\leq k\leq n$ . Moreover, we characterize the extremal graphs with equality holding. Finally, we show that $λ_n(A_α({G}))\geq 2α-1$ if $G$ contains no isolated vertices.

preprint2020arXiv

The maximum spectral radius of wheel-free graphs

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, Nikiforov proposed a Brualdi-Solheid-Turán type problem: what is the maximum spectral radius of a graph of order $n$ that does not contain subgraphs of particular kind. In this paper, we study the Brualdi-Solheid-Turán type problem for wheel-free graphs, and we determine the maximum (signless Laplacian) spectral radius of a wheel-free graph of order $n$ . Furthermore, we characterize the extremal graphs.

preprint2016arXiv

The distance spectra of the derangement graphs

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 obtain their distance spectra. In particular, we determine all their extremal distance eigenvalues.

preprint2015arXiv

Remoteness and distance eigenvalues of a graph

Let $G$ be a connected graph of order $n$ with diameter $d$ . Remoteness $ρ$ of $G$ is the maximum average distance from a vertex to all others and $\partial_1\geq\cdots\geq \partial_n$ are the distance eigenvalues of $G$ . In \cite{AH}, Aouchiche and Hansen conjectured that $ρ+\partial_3>0$ when $d\geq 3$ and $ρ+\partial_{\lfloor\frac{7d}{8}\rfloor}>0.$ In this paper, we confirm these two conjectures. Furthermore, we give lower bounds on $\partial_n+ρ$ and $\partial_1-ρ$ when $G\ncong K_n$ and the extremal graphs are characterized.

preprint2013arXiv

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

Let $G$ be a graph with $n$ vertices and $λ_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 without given pathes or cycles and determine the extremal graphs. This result gives spectral conditions for the existence of specified paths and cycles in graphs.

Huiqiu Lin

Research overview

Is this your work?

14 publications

More on spectral supersaturation for the bowtie

Eigenvalues of signed graphs

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

Spectral radius and edge-disjoint spanning trees

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

Toughness, hamiltonicity and spectral radius in graphs

A Complete Solution to the Cvetković-Rowlinson Conjecture

Perfect matching and distance spectral radius in graphs and bipartite graphs

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

On the $A_α$ -spectra of graphs

The maximum spectral radius of wheel-free graphs

The distance spectra of the derangement graphs

Remoteness and distance eigenvalues of a graph

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

See the researcher in context

Building this map preview

Huiqiu Lin

Research overview

Is this your work?

14 publications

More on spectral supersaturation for the bowtie

Eigenvalues of signed graphs

Spectral radius and (globally) rigidity of graphs in R2R^2R2

Spectral radius and edge-disjoint spanning trees

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

Toughness, hamiltonicity and spectral radius in graphs

A Complete Solution to the Cvetković-Rowlinson Conjecture

Perfect matching and distance spectral radius in graphs and bipartite graphs

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

On the AαA_αAα​-spectra of graphs

The maximum spectral radius of wheel-free graphs

The distance spectra of the derangement graphs

Remoteness and distance eigenvalues of a graph

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

See the researcher in context

Building this map preview

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

On the $A_α$ -spectra of graphs