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$.
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.
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)$.
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.
For a graph $G$ of order $n$, with adjacency eigenvalues $\lambda_1(G) \geq \cdots \geq \lambda_n(G)$, the \emph{energy} of $G$ is defined to be \[\mathcal{E}(G)=\sum_{i=1}^{n} |\lambda_i(G)|.\] A well-known conjecture from the 1980s by Fajtlowicz states that for any graph $G$, \[\mathcal{E}(G) \ge 2\left(n-\alpha(G)\right),\] where $\alpha(G)$ denotes the independence number. We prove this conjecture.
For a graph $G$, let $ \lambda_1(G)\ge \lambda_2(G)\ge \cdots \ge \lambda_n(G)$ denote the adjacency eigenvalues of $G$. We investigate the asymptotic maximum of \[ \lambda_i(G)+\lambda_j(\overline G) \] for fixed $i$ and $j$. We prove general bounds on $\lambda_i(G) + \lambda_{j}(\overline{G})$ for all pairs $(i, j)$ and also give general bounds on the related problem of minimizing $\lambda_{n-i+1}(G) + \lambda_{n-j+1}(\overline{G})$ for fixed $i$ and $j$. We prove that for all looped graphs $G$ on $n$ vertices, \[\lambda_1(G) + \lambda_2(\overline{G}) \le \frac87 n. \] Our method also gives a new short proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that $\lambda_1(G) + \lambda_1(\overline{G}) \le \frac43n - 1$. We also show the close relation of these Nordhaus-Gaddum type problems to recent work on the maximum spectral gaps of graphs by Brooks, Linz and Lu.
Sahil Agarwal, Carter Antley, Joseph Aulenbacher et al.· 1 citation· ⚡1
For a graph $G$ of order $n$, let $\mathcal E(G)$ denote its adjacency energy and let $\alpha(G)$ denote its independence number. A recent theorem of Kumar and Pragada states that $$\mathcal E(G)\ge 2\bigl(n-\alpha(G)\bigr).$$ We determine all graphs attaining equality. More precisely, equality holds if and only if every connected component of $G$ is an isolated vertex, a balanced complete multipartite graph, or a graph obtained by taking the disjoint union of $K_{a,\ldots,a}$ and $K_{b,\ldots,b}$, with the same number $r\ge3$ of parts, and then completely joining corresponding parts.
S. A. Mojallal· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
