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.
Let $G$ be a connected graph, and let $\lambda_1(G)>\lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the comple...
Let $G$ be a graph of order $n$, and let $s^+(G)$ and $s^-(G)$ denote the sums of the squares of the positive and negative adjacency eigenvalues of $G$, respectively. Recently, Liu, Tang, and Zhang proved the conjecture of Elphick, Farber, Goldberg, and Wocjan that every connected graph $G$ of order $n$ satisfies $ \mi...
Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{...
Let $G$ be a simple graph on $n$ vertices, and let $F(G)$ denote the number of its spanning forests. Bencs and Csikv\'ari [Upper bound for the number of spanning forests of regular graphs, European J. Combin. 110 (2023) 103677] proved that every $r$-regular graph $G$ with $r\geq 2$ satisfies $F(G) \leq r^{n}$. They fur...
Ting-Zeng Wu, S. Lu, Xiang-Shuai Dong· 0 citations
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
We consider a random subgraph $G_p(n,r,<s)$ of the complete distance graph $G(n,r,<s)$ whose vertices are the $r$-element subsets of the set $\{1,\dots,n\}$ and whose edges join pairs of subsets that intersect in fewer than $s$ elements; each edge survives independently of the others with probability $p$. The independe...
V. A. Pokhachevskiy, Andrei M. Raigorodskii· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
