For an integer $k\ge2$, let $\lambda_k(G)$ denote the $k$th largest adjacency eigenvalue of a graph $G$. For every graph $G$ on $n$ vertices and every $2 \leq k \leq n$, we prove \[ \lambda_k(G) \le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1. \] Our bound is tight for $k\in\{2,3,4,8,24\}$. We obtain it by reducing the graph-eigenvalue problem to an extremal problem for orthogonal projections and then applying the general upper bound on the absolute projection constant $\gamma(r)$ due to Der\k{e}gowska and Lewandowska. We also give an alternative proof of their bound by repairing the Gegenbauer-polynomial argument of K\"onig and Tomczak-Jaegermann. The resulting slack identity yields a strict improvement in every even dimension $r\ge4$ for which $r+2$ is not a perfect square.
For a simple graph $G$ of order $n$, let $\lambda_1(G)\ge \cdots \ge \lambda_n(G)$ denote its adjacency eigenvalues. Hong's problem asks for the optimal upper bound for $\lambda_k(G)$. A recent theorem of Sivashankar gives, for every $k\ge3$, \[ \lambda_k(G)\le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1, \] with sharp examples arising from maximal real equiangular tight frames. In this paper, we characterize the equality case. We also obtain an explicit combinatorial description of the extremal graphs for $\lambda_3$ and $\lambda_4$.
Hitesh Kumar, Bojan Mohar, S. A. Mojallal et al.· 0 citations
Let $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n$ be the eigenvalues of a simple graph $G$ of order $n$. The HL-index of $G$ is defined by $R(G)=\max\|\lambda_h|,|\lambda_\ell|\}$ with $h=\lfloor(n+1)/2\rfloor$ and $\ell=\lceil(n+1)/2\rceil$.In this paper, we prove that if $G$ is $ K_4$-minor-free or $ K _ {2,3} $-minor-free, then $R(G)\leq\sqrt{5}-1$ with equality attained by an infinite family of outerplanar graphs.Moreover, we show that $R(G)\leq\sqrt{d-2}$ for triangle-free graphs with maximum degree at most $d$ and average degree at most $(d-2)(d^2-2d+2)/(d^2-3d+5)$.
Let $S_k(G)$ denote the sum of the $k$ largest Laplacian eigenvalues of a connected graph $G$ of order $n$ and size $m$. Write $\mathrm{PA}_{n,\omega}$ for the graph obtained from an $\omega$-vertex clique by attaching $n-\omega$ pendant vertices to one of its vertices, and set \[ M_{n,k}:=\binom{k+1}{2}+n-k-1, \] the number of edges of $\mathrm{PA}_{n,k+1}$. For $n/2<k\le n-2$, we prove the sharp bound \[ S_k(G)\le \frac{2k}{n}m+ \frac{2(n-k)}{n}M_{n,k}-(n-k-1), \] with equality attained by $\mathrm{PA}_{n,k+1}$. This bound is complementary to Brouwer's inequality and is strictly stronger when $m<M_{n,k}$. Combining our bound with Brouwer's inequality, we resolve and strengthen a conjecture of Vinagre, Del-Vecchio, Justo, and Trevisan: for every $n$, the pineapple $\mathrm{PA}_{n,1+\lfloor2n/3\rfloor}$ maximizes the Laplacian energy among all connected graphs of order $n$; moreover, for $n>4$, it is the unique maximizer.
For a fixed integer $k\ge2$, we establish a sharp adjacency-spectral upper bound for sufficiently large $m$-edge $kK_3$-free graphs. We prove \[ \lambda(G)\le (k-1)+\sqrt{m-k(k-1)}. \] Moreover, equality holds precisely when $(2k-1)\mid m$ and, up to isolated vertices, $G$ is the join of $K_{2k-1}$ with an independent set of $m/(2k-1)-(k-1)$ vertices. The case $k=2$ was previously known; our argument establishes every fixed $k\ge3$. The proof requires information beyond first-order spectral stability. We derive an exact nonnegative defect identity at a maximum Perron vertex, use it to bound the entire outer layer by a constant, and reduce the remaining graph to a bounded core with finitely many independent twin classes. A Perron-vector concentration identity and the Erd\H{o}s--Gallai matching theorem then force the unique extremal core. A nearly extremal family lies only $\Theta(m^{-1/2})$ below the target, showing why an exact second-order analysis is necessary.
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the sum of the largest Laplacian eigenvalues of graphs, {\em Discrete Appl. Math.}, 170:95--103, (2014)], Rocha and Trevisan showed that the conjecture holds true for $1 \leq k \leq \lfloor g/5 \rfloor$, where $g$ denotes the girth of $G$. This bound on $k$ was later improved by Chen in [Improved results on Brouwers conjecture for sum of the Laplacian eigenvalues of a graph, {\em Linear Algebra Appl.}, 557:327--338, (2018)], who established that the conjecture holds for $1 \leq k \leq \lfloor g/4 \rfloor$. In this article, we further strengthen these results by proving that the Brouwers conjecture holds for $1\leq k\leq\left\lfloor \frac{m(G)}{2}\right\rfloor,$ where $m(G)$ denotes the matching number of $G$. Since $m(G)\geq \lfloor g/2\rfloor$, the case constitutes a genuine improvement over the aforementioned results. As an application, we show that if $G$ is a graph of order $n$ and with a perfect matching, then the Brouwers conjecture holds for $1\leq k\leq \left\lfloor \frac{n}{4}\right\rfloor$. Finally, we provide a new perspective on verifying Brouwers conjecture by proving that $G$ satisfies the Brouwers conjecture if and only if for a fixed positive integer $h$, $\mathcal{S}_h(\overline{G})\leq e(\overline{G})+\binom{h+1}{2}$ holds whenever $\mathcal{S}_h(G)\leq e(G)+\binom{h+1}{2}$, where $\overline{G}$ denotes the complement of $G$.
For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche--Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.
Jingfan Huang, Wei Wei· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
