Let $G=(V,E)$ be a finite simple graph with Laplacian eigenvalues $\lambda_1(L(G))\ge\cdots\ge\lambda_{|V|}(L(G))$, and define \[ \eps_k(G)= \sum_{j=1}^{\min\{k,|V|\}}\lambda_j(L(G))-|E|. \] Let $\nu(G)$ be the matching number of $G$, and let $n(G)$ be the number of non-isolated vertices of $G$. Lew proved that \(\eps_k(G)\le k\nu(G)+\lfloor k/2\rfloor\), and conjectured that the additive term can be removed in the non-endpoint range. We prove this conjecture: \[ \eps_k(G)\le k\nu(G) \qquad (1\le k\le n(G)-2). \] We also characterize all equality cases. Up to isolated vertices, equality holds precisely for stars, for \(K_1\vee(K_k\cup\overline{K_{n-k-1}})\) with \(k\) odd, and for \(K_n-E(K_{1,t})\) with \(n\) odd, \(k=n-2\), and \(1\le t\le n-2\). We also analyze the endpoint range \(k\ge n(G)-1\), where \(\eps_k(G)=|E|\), and determine the specific cases where the inequality \(\varepsilon_k(G)\le k\nu(G)\) fails or holds with equality.
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 su...
Let $G$ be a graph of order $n$ with the adjacency eigenvalues $\lambda_1(G) \geq \dots \geq \lambda_n(G) $. Let $c(v)$ denote the maximum order of a clique containing vertex $v$. We prove the vertex-localized positive square-energy inequality \[ \sqrt{s_+(G)} \leq \sum_{v\in V}\left(1-\frac1{c(v)}\right), \] where \[...
Abhay Jayarajan, M. Kannan, Shivaramakrishna Pragada 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} $-mi...
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)\r...
Let $G$ be an $n$-vertex graph with $e(G)$ edges, and let $\lambda(G)$ denote the largest eigenvalue of its adjacency matrix. The booksize $\mathrm{bk} (G)$ of $G$ is defined as the largest number of triangles sharing a common edge. The main purpose of this note is to prove that if $\lambda(G)\geq\lambda(T_{n,2})$ and...
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 exam...
Hitesh Kumar, Bojan Mohar, S. A. Mojallal et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
