The $\text{bk}(G)$ of a graph $G$ is the maximum number of triangles sharing a common edge. Motivated by a classical conjecture of Erd\H{o}s, spectral lower bounds for the booksize have received considerable attention. For a positive divisor $s$ of $m-1$ with $\frac{m-1}{s}\ge2$, let $S_{m,s}^{+}$ be obtained from $K_{s,\frac{m-1}{s}}$ by adding one edge inside the part of order $\frac{m-1}{s}$. Zhai et al. proved that, apart from this explicit family, every $m$-edge non-bipartite graph satisfying $\rho(G)^2\ge m-1+\frac{2}{\rho(G)-1}$ has booksize greater than $\frac{1}{240}\sqrt{m}$, and they asked for the best possible constant. We answer this question asymptotically. For every $0<\varepsilon<\frac{1}{4}$ and all sufficiently large $m$, every $m$-edge non-bipartite graph $G$ without isolated vertices satisfying the same spectral condition either is isomorphic to $S_{m,s}^{+}$ for some such integer $s$, or satisfies $\text{bk}(G)>\left(\frac{1}{4}-\varepsilon\right)\sqrt{m}$. We also give infinitely many graphs outside the exceptional family showing that no constant larger than $\frac{1}{4}$ is possible. Thus $\frac{1}{4}$ is the optimal asymptotic constant in the problem of Zhai et al.
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 an $F$-free graph $G$, a non-edge is $F$-saturating if adding it to $G$ creates a copy of $F$. We denote by $f_{p+1}(n,m)$ the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free $n$-vertex graph with $m$ edges. Erd\H{o}s and Tuza conjectured that $f_4\left(n,\mathrm{ex}(n,K_3)+ 1\right)= (1 + o(1)...
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...
A classical result of Andr\'asfai, Erd\H{o}s, and S\'os states that every $n$-vertex graph with odd girth at least $2k+1$ and minimum degree larger than $\frac{2n}{2k+1}$ is bipartite. Rather than imposing a minimum-degree condition, in this paper we investigate conditions on algebraic connectivity that force graphs of...
Given graphs $H$ and $F$, the generalized Tur\'{a}n number ${\rm ex}(n,H,F)$ is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Alon and Shikhelman (J. Combin. Theory Ser. B, 2016) initiated the systematic study of generalized Tur\'{a}n problems. Let $T$ be a tree on $k$ vertices, and write $n=a(k-...
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...
S. A. Mojallal· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
