Search

Recently, Ning and Zhai (2023) proved that every $n$-vertex graph $G$ with $\lambda (G) \ge \sqrt{\lfloor n^2/4\rfloor}$ has at least $\lfloor n/2\rfloor -1$ triangles, unless $G=K_{\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor}$. The aim of this paper is two-fold. Using the supersaturation-stability method, we prove a stability variant of Ning-Zhai's result by showing that such a graph $G$ contains at least $n-3$ triangles if no vertex is in all triangles of $G$. This result could also be viewed as a spectral version of a result of Xiao and Katona (2021). The second part concerns with the spectral supersaturation for the bowtie, which consists of two triangles sharing a common vertex. A theorem of Erd\H{o}s, F\"{u}redi, Gould and Gunderson (1995) says that every $n$-vertex graph with more than $\lfloor n^2/4\rfloor +1$ edges contains a bowtie. For graphs of given order, the spectral supersaturation problem has not been considered for substructures that are not color-critical. In this paper, we give the first such theorem by counting the number of bowties. Let $K_{\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor}^{+2}$ be the graph obtained from $K_{\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor}$ by embedding two disjoint edges into the vertex part of size $\lceil \frac{n}{2} \rceil$. Our result shows that every graph $G$ with $n\ge 8.8 \times 10^6$ vertices and $\lambda (G)\ge \lambda (K_{\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor}^{+2})$ contains at least $\lfloor \frac{n}{2} \rfloor$ bowties, and $K_{\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor}^{+2}$ is the unique spectral extremal graph. This gives a spectral correspondence of a theorem of Kang, Makai and Pikhurko (2020). The method used in our paper provides a probable way to establish the spectral counting results for other graphs, even for non-color-critical graphs., Comment: 32 pages. Some spectral extremal graph problems are proposed in the end. Any suggestions are welcome. arXiv admin note: text overlap with arXiv:2406.13176

A well-known theorem of Mantel states that every $n$-vertex graph with more than $\lfloor n^2/4\rfloor $ edges contains a triangle. An interesting problem in extremal graph theory studies the minimum number of edges contained in triangles among graphs with a prescribed number of vertices and edges. Erd\H{o}s, Faudree and Rousseau (1992) showed that a graph on $n$ vertices with more than $\lfloor n^2/4\rfloor $ edges contains at least $2\lfloor n/2\rfloor +1$ edges in triangles. Such edges are called triangular edges. In this paper, we present a spectral version of the result of Erd\H{o}s, Faudree and Rousseau. Using the supersaturation-stability and the spectral technique, we prove that every $n$-vertex graph $G$ with $\lambda (G) \ge \sqrt{\lfloor n^2/4\rfloor}$ contains at least $2 \lfloor {n}/{2} \rfloor -1$ triangular edges, unless $G$ is a balanced complete bipartite graph. The method in our paper has some interesting applications. Firstly, the supersaturation-stability can be used to revisit a conjecture of Erd\H{o}s concerning with the booksize of a graph, which was initially proved by Edwards (unpublished), and independently by Khad\v{z}iivanov and Nikiforov (1979). Secondly, our method can improve the bound on the order $n$ of a graph by dropping the condition on $n$ being sufficiently large, which is obtained from the triangle removal lemma. Thirdly, the supersaturation-stability can be applied to deal with the spectral extremal graph problems on counting triangles, which was recently studied by Ning and Zhai (2023)., Comment: 30 pages. At the end of the paper, we proposed many spectral extremal graph problems for readers. Any comments are welcome

A classical result of Erd\H{o}s and Rademacher (1955) indicates a supersaturation phenomenon. It says that if $G$ is a graph on $n$ vertices with at least $\lfloor {n^2}/{4} \rfloor +1$ edges, then $G$ contains at least $\lfloor {n}/{2}\rfloor$ triangles. We prove a spectral version of Erd\H{o}s--Rademacher's theorem. Moreover, Mubayi [Adv. Math. 225 (2010)] extends the result of Erd\H{o}s and Rademacher from a triangle to any color-critical graph. It is interesting to study the extension of Mubayi from a spectral perspective. However, it is not apparent to measure the increment on the spectral radius of a graph comparing to the traditional edge version (Mubayi's result). In this paper, we provide a way to measure the increment on the spectral radius of a graph and propose a spectral version on the counting problems for color-critical graphs., Comment: 27 pages, 5 figures. Any comments and suggestions are welcome

High-entropy alloys (HEAs) and their corresponding high-entropy hydrides are new potential candidates for negative electrode materials of nickel-metal hydride (Ni-MH) batteries. This study investigates the cyclic electrochemical hydrogen storage performance of two AB-type HEAs (A: hydride-forming elements, B: non-hydride-forming elements) in Ni-MH batteries. TiV2ZrCrMnFeNi with a dual-phase structure shows a fast activation and a low charge transfer impedance with a discharge capacity of 150 mAhg-1, while TiV1.5Zr1.5CrMnFeNi with a single phase shows a slow activation and a capacity of only 60 mAhg-1. The better electrochemical performance of TiV2ZrCrMnFeNi was attributed to its higher vanadium/zirconium ratio and abundant interphase boundaries, which act as hydrogen paths and heterogeneous hydride nucleation sites. These results suggest the high potential of dual-phase HEAs as new active electrode materials for Ni-MH batteries.

A well-known result of Nosal states that a graph $G$ with $m$ edges and $\lambda(G) > \sqrt{m}$ contains a triangle. Nikiforov [Combin. Probab. Comput. 11 (2002)] extended this result to cliques by showing that if $\lambda (G) > \sqrt{2m(1-1/r)}$, then $G$ contains a copy of $K_{r+1}$. Let $C_k^+$ be the graph obtained from a cycle $C_k$ by adding an edge to two vertices with distance two, and let $F_k$ be the friendship graph consisting of $k$ triangles that share a common vertex. Recently, Zhai, Lin and Shu [European J. Combin. 95 (2021)], Sun, Li and Wei [Discrete Math. 346 (2023)], and Li, Lu and Peng [Discrete Math. 346 (2023)] proved that if $ m\ge 8$ and $\lambda (G) \ge \frac{1}{2} (1+\sqrt{4m-3})$, then $G$ contains a copy of $C_5,C_5^+$ and $F_2$, respectively, unless $G=K_2\vee \frac{m-1}{2}K_1$. In this paper, we give a unified extension by showing that such a graph contains a copy of $V_5$, where $V_5=K_1\vee P_4$ is the join of a vertex and a path on four vertices. Our result extends the aforementioned results since $C_5,C_5^+$ and $F_2$ are proper subgraphs of $V_5$. In addition, we prove that if $m\ge 33$ and $\lambda (G) \ge 1+ \sqrt{m-2}$, then $G$ contains a copy of $F_3$, unless $G=K_3\vee \frac{m-3}{3}K_1$. This confirms a conjecture on the friendship graph $F_k$ in the case $k=3$. Finally, we conclude some spectral extremal graph problems concerning the large fan graphs and wheel graphs., Comment: 21 pages,2 figures

In this paper, we derive a tight upper bound for the size of an intersecting $k$-Sperner family of subspaces of the $n$-dimensional vector space $\mathbb{F}_{q}^{n}$ over finite field $\mathbb{F}_{q}$ which gives a $q$-analogue of the Erd\H{o}s' $k$-Sperner Theorem, and we then establish a general relationship between upper bounds for the sizes of families of subsets of $[n] = \{1, 2, \dots, n\}$ with property $P$ and upper bounds for the sizes of families of subspaces of $\mathbb{F}_{q}^{n}$ with property $P$, where $P$ is either $\mathcal{L}$-intersecting or forbidding certain configuration. Applying this relationship, we derive generalizations of the well known results about the famous Erd\H{o}s matching conjecture and Erd\H{o}s-Chv\'atal simplex conjecture to linear lattices. As a consequence, we disprove a related conjecture on families of subspaces of $\mathbb{F}_{q}^{n}$ by Ihringer [Europ. J. Combin., 94 (2021), 103306].

A theorem of Nosal and Nikiforov states that if $G$ is a triangle-free graph with $m$ edges, then $\lambda (G)\le \sqrt{m}$, where the equality holds if and only if $G$ is a complete bipartite graph. A well-known spectral conjecture of Bollob\'{a}s and Nikiforov [J. Combin. Theory Ser. B 97 (2007)] asserts that if $G$ is a $K_{r+1}$-free graph with $m$ edges, then $\lambda_1^2(G) + \lambda_2^2(G) \le (1-\frac{1}{r})2m$. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] confirmed the conjecture in the case $r=2$. Using this base case, they proved further that $\lambda (G)\le \sqrt{m-1}$ for every non-bipartite triangle-free graph $G$, with equality if and only if $m=5$ and $G=C_5$. Moreover, Zhai and Shu [Discrete Math. 345 (2022)] presented an improvement by showing $\lambda (G) \le \beta (m)$, where $\beta(m)$ is the largest root of $Z(x):=x^3-x^2-(m-2)x+m-3$. The equality in Zhai--Shu's result holds only if $m$ is odd and $G$ is obtained from the complete bipartite graph $K_{2,\frac{m-1}{2}}$ by subdividing exactly one edge. Motivated by this observation, Zhai and Shu proposed a question to find a sharp bound when $m$ is even. We shall solve this question by using a different method and characterize three kinds of spectral extremal graphs over all triangle-free non-bipartite graphs with even size. Our proof technique is mainly based on applying Cauchy interlacing theorem of eigenvalues of a graph, and with the aid of a triangle counting lemma in terms of both eigenvalues and the size of a graph., Comment: 28 pages. Following reviewer's suggestion, we have changed the original title. arXiv admin note: text overlap with arXiv:2204.09884

The Tur\'an number $\mathrm{ex}(n,H)$ of a graph $H$ is the maximum number of edges in an $n$-vertex graph which does not contain $H$ as a subgraph. The Tur\'{a}n number of regular polyhedrons was widely studied in a series of works due to Simonovits. In this paper, we shall present the exact Tur\'{a}n number of the prism $C_{2k+1}^{\square} $, which is defined as the Cartesian product of an odd cycle $C_{2k+1}$ and an edge $ K_2 $. Applying a deep theorem of Simonovits and a stability result of Yuan [European J. Combin. 104 (2022)], we shall determine the exact value of $\mathrm{ex}(n,C_{2k+1}^{\square})$ for every $k\ge 1$ and sufficiently large $n$, and we also characterize the extremal graphs. Moreover, in the case of $k=1$, motivated by a recent result of Xiao, Katona, Xiao and Zamora [Discrete Appl. Math. 307 (2022)], we will determine the exact value of $\mathrm{ex}(n,C_{3}^{\square} )$ for every $n$ instead of for sufficiently large $n$., Comment: 24 pages

Let $F_s$ be the friendship graph obtained from $s$ triangles by sharing a common vertex. For fixed $s\ge 2$ and sufficiently large $n$, the $F_s$-free graphs of order $n$ which attain the maximal spectral radius was firstly characterized by Cioab\u{a}, Feng, Tait and Zhang [Electron. J. Combin. 27 (4) (2020)],and later uniquely determined by Zhai, Liu and Xue [Electron. J. Combin. 29 (3) (2022)]. Recently, the spectral extremal problems was widely studied for graphs containing no $H$ as a minor. For instance, Tait [J. Combin. Theory Ser. A 166 (2019)], Zhai and Lin [J. Combin. Theory Ser. B 157 (2022)] solved the case $H=K_r$ and $H=K_{s,t}$, respectively. Motivated by these results, we consider the spectral extremal problems in the case $H=F_s$. We shall prove that $K_s \vee I_{n-s}$ is the unique graph that attain the maximal spectral radius over all $n$-vertex $F_s$-minor-free graphs. Moreover, let $Q_t$ be the graph obtained from $t$ copies of the cycle of length $4$ by sharing a common vertex. We also determine the unique $Q_t$-minor-free graph attaining the maximal spectral radius. Namely, $K_t \vee M_{n-t}$, where $M_{n-t}$ is a graph obtained from an independent set of order $n-t$ by embedding a matching consisting of $\lfloor \frac{n-t}{2}\rfloor$ edges.

Let $F_k$ be the (friendship) graph obtained from $k$ triangles by sharing a common vertex. The $F_k$-free graphs of order $n$ which attain the maximal spectral radius was firstly characterized by Cioab\u{a}, Feng, Tait and Zhang [Electron. J. Combin. 27 (4) (2020)], and later uniquely determined by Zhai, Liu and Xue [Electron. J. Combin. 29 (3) (2022)] under the condition that $n$ is sufficiently large. In this paper, we get rid of the condition on $n$ being sufficiently large if $k=2$. The graph $F_2$ is also known as the bowtie. We show that the unique $n$-vertex $F_2$-free spectral extremal graph is the balanced complete bipartite graph adding an edge in the vertex part with smaller size if $n\ge 7$, and the condition $n\ge 7$ is tight. Our result is a spectral generalization of a theorem of Erd\H{o}s, F\"{u}redi, Gould and Gunderson [J. Combin. Theory Ser. B 64 (1995)], which states that $\mathrm{ex}(n,F_2)=\left\lfloor {n^2}/{4} \right\rfloor +1$. Moreover, we study the spectral extremal problem for $F_k$-free graphs with given number of edges. In particular, we show that the unique $m$-edge $F_2$-free spectral extremal graph is the join of $K_2$ with an independent set of $\frac{m-1}{2}$ vertices if $m\ge 8$, and the condition $m\ge 8$ is tight., Comment: 22 pages, 6 figures. This is the published version

Let $C_k^{\triangle}$ be the graph obtained from a cycle $C_{k}$ by adding a new vertex connecting two adjacent vertices in $C_{k}$. In this note, we obtain the graph maximizing the spectral radius among all graphs with size $m$ and containing no subgraph isomorphic to $C_6^{\triangle}$. As a byproduct, we will show that if the spectral radius $\lambda(G)\ge1+\sqrt{m-2}$, then $G$ must contains all the cycles $C_i$ for $3\le i\le 7$ unless $G\cong K_3\nabla \left(\frac{m-3}{3}K_1\right)$., Comment: 12 pages, 1 figure

It is well-known that eigenvalues of graphs can be used to describe structural properties and parameters of graphs. A theorem of Nosal states that if $G$ is a triangle-free graph with $m$ edges, then $\lambda (G)\le \sqrt{m}$, equality holds if and only if $G$ is a complete bipartite graph. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] proved a generalization for non-bipartite triangle-free graphs. Moreover, Zhai and Shu [Discrete Math. 345 (2022)] presented a further improvement. In this paper, we present an alternative method for proving the improvement by Zhai and Shu. Furthermore, the method can allow us to give a refinement on the result of Zhai and Shu for non-bipartite graphs without short odd cycles., Comment: 27 pages, 6 figures. We would like to express sincere thanks to Huiqiu Lin, Bo Ning and Mingqing Zhai for kind discussions, which considerably improves the presentation of the manuscript. The present work can be viewed as the second paper of our previous project arXiv:2204.09194. Any comments and suggestions are welcome

A well-known result in extremal spectral graph theory, due to Nosal and Nikiforov, states that if $G$ is a triangle-free graph on $n$ vertices, then $\lambda (G) \le \lambda (K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil })$, equality holds if and only if $G=K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil }$. Nikiforov [Linear Algebra Appl. 427 (2007)] extended this result to $K_{r+1}$-free graphs for every integer $r\ge 2$. This is known as the spectral Tur\'{a}n theorem. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] proved a refinement on this result for non-bipartite triangle-free graphs. In this paper, we provide alternative proofs for the result of Nikiforov and the result of Lin, Ning and Wu. Our proof can allow us to extend the later result to non-$r$-partite $K_{r+1}$-free graphs. Our result refines the theorem of Nikiforov and it also can be viewed as a spectral version of a theorem of Brouwer., Comment: 26 pages, 6 figures. Any comments and suggestions are welcome. This article was completed during a quarantine period due to the COVID-19 pandemic. The authors would like to express their sincere gratitude to all of the volunteers and medical staffs for their kind help and support, which makes our daily life more and more secure

Both the Simonovits stability theorem and the Nikiforov spectral stability theorem are powerful tools for solving exact values of Tur\'{a}n numbers in extremal graph theory. Recently, F\"{u}redi [J. Combin. Theory Ser. B 115 (2015)] provided a concise and contemporary proof of the Simonovits stability theorem. In this note, we present a unified treatment for some extremal graph problems, including short proofs of Nikiforov's spectral stability theorem and the clique stability theorem proved recently by Ma and Qiu [European J. Combin. 84 (2020)]. Moreover, some spectral extremal problems related to the $p$-spectral radius and signless Laplacian radius are also included., Comment: 25 pages. At the end of the paper, we proposed an open problem. Any suggestions and comments are welcome! The first author would like to thank Prof. Lihua Feng, who introduced and encouraged him to the study of fascinating spectral graph theory. Thanks also go to Prof. Vladimir Nikiforov for valuable comments and for pointing out references [51,22]

We study matrix inequalities involving partial traces for positive semidefinite block matrices. First of all, we present a new method to prove a celebrated result of Choi [Linear Algebra Appl. 516 (2017)]. Our method also allows us to prove a generalization of another result of Choi [Linear Multilinear Algebra 66 (2018)]. Furthermore, we shall give an improvement on a recent result of Li, Liu and Huang [Operators and Matrices 15 (2021)]. In addition, we include with some majorization inequalities involving partial traces for two by two block matrices, and also provide inequalities related to the unitarily invariant norms as well as the singular values, which can be viewed as slight extensions of two results of Lin [Linear Algebra Appl. 459 (2014)] and [Electronic J. Linear Algebra 31 (2016)]., Comment: We have reduced the paper to 16 pages. The author would like to thank Prof. Minghua Lin for bringing the topic on partial traces to his attention. Thanks also go to Prof. Fuzhen Zhang and Prof. Yuejian Peng for valuable comments which improve the presentation. The author is also grateful to Prof. Tsuyoshi Ando for the correspondence [3] before its publication, which initiates our research. Linear and Multilinear Algebra, 2022

This survey is two-fold. We first report new progress on the spectral extremal results on the Tur\'{a}n type problems in graph theory. More precisely, we shall summarize the spectral Tur\'{a}n function in terms of the adjacency spectral radius and the signless Laplacian spectral radius for various graphs. For instance, the complete graphs, general graphs with chromatic number at least three, complete bipartite graphs, odd cycles, even cycles, color-critical graphs and intersecting triangles. The second goal is to conclude some recent results of the spectral conditions on some graphical properties. By a unified method, we present some sufficient conditions based on the adjacency spectral radius and the signless Laplacian spectral radius for a graph to be Hamiltonian, $k$-Hamiltonian, $k$-edge-Hamiltonian, traceable, $k$-path-coverable, $k$-connected, $k$-edge-connected, Hamilton-connected, perfect matching and $\beta$-deficient., Comment: This article is a survey paper and it is very long with 80 pages. In such survey, it is impossible to refer to all the nice papers. So if a paper is missing from this survey, which does not mean that it is not worth including it. Any suggestions and comments are welcome. E-mail: ytli0921@hnu.edu.cn