Skip to content
Preprint

Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs

Sep 2026 · 0 citations · 49 references
Mathematics

Abstract

Spectral Tur\'an-type problems ask how the absence of prescribed subgraphs constrains the spectral radius of a matrix associated with a graph. Given a family of graphs $\mathcal{F}$, a graph is called $\mathcal{F}$-free if it contains no member of $\mathcal{F}$ as a subgraph. The theta graph $\theta(l_1,\ldots,l_k)$ consists of $k$ internally disjoint paths of lengths $l_1,\ldots,l_k$ with two common end vertices. In this paper, we study two spectral Tur\'an-type extremal problems for the signless Laplacian spectral radius. First, among all $\{C_3,C_4\}$-free graphs of fixed order with no pendant vertices, we determine the maximum signless Laplacian spectral radius and uniquely characterize the extremal graph attaining it. The extremal structure exhibits a parity phenomenon: odd and even orders give rise to two distinct graph families. These results, in particular, sharpen a recent general upper bound for this class given by Liu and Wang (2026). Next, we obtain the corresponding extremal results for all $\{\theta(1,2,2),\theta(1,2,3)\}$-free graphs of fixed size with no pendant vertices when the size is congruent to $1$ modulo $3$ and $2$ modulo $3$, again obtaining unique but structurally different maximizing graphs in the two cases. Together with the previously known result for sizes congruent to $0$ modulo $3$ by Liu and Wang (2026), this completes the fixed-size problem across all three congruence classes modulo $3$.

View source

Similar papers

Preprint Aug 2026

Spectral extrema of 1-planar graphs with no short cycles or small cliques

The spectral Tur\'an type problem, initiated by Nikiforov in 2007, aims to determine the graphs among $n$-vertex $H$-free graphs having maximum spectral radius. In this paper, we study this problem for $1$-planar graphs, i.e., graphs that admit a drawing in the plane such that each edge is crossed at most once. Recentl...

Shuchao Li, Mingli Wang, Qin Zhao · 2 citations · ⚡1
Preprint Aug 2026

Homomorphism and VC-dimension thresholds: spectra and separations

Minimum-degree thresholds ask when excluding a fixed graph $H$ forces a dense graph to admit a simple global description. For each fixed chromatic number, the chromatic threshold has only three possible values. We show that this finite-spectrum phenomenon is special to chromatic threshold: already among $3$-chromatic g...

Lior Gishboliner, Xin-Qi Huang, Hong Liu · 1 citation
Preprint Aug 2026

On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs

In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface of genus $g\ge 1$. In particular, for such a graph $G$ with $n$ vertices and maximum degree $\Delta$, we show that the second-smallest eige...

Benedikt Kolbe, Jack Spalding-Jamieson · 0 citations
Preprint Aug 2026

Structure theorems for Lichnerowicz-sharp graphs

Hypercube graphs are fundamental model spaces of positive curvature in discrete comparison geometry. Let $G$ be a finite, connected, simple, unweighted graph with Bakry--\'Emery curvature bounded below by $K$. We call $G$ Lichnerowicz-sharp if its first non-zero non-normalized Laplacian eigenvalue $\lambda_1=K$. We pro...

Yanlong Ding, Shiping Liu, Chiyu Zhou · 0 citations
Preprint Sep 2026

Nonregular graphs of odd maximum degree with maximum spectral radius

Let $\rho(n,d)$ denote the maximum adjacency spectral radius among all connected nonregular graphs of order $n$ and maximum degree $d$. A graph attaining this maximum is called an extremal graph. Liu [J. Combin. Theory Ser. B, 2024] determined the extremal graphs for $d=3,4$ and formulated two conjectures for general $...

Liang-Dong Fan, Li-Ying Kang, Yao-Jun Chen · 0 citations
Preprint Aug 2026

Unbalanced Tur\'an and spectral Tur\'an problems with prescribed large maximum degree

Classical Tur\'an theory shows that, without additional constraints, the extremal structure of $F$-free graphs is governed by the chromatic number of $F$ and is asymptotically the balanced Tur\'an graph. We investigate how prescribing a large maximum degree changes this picture and leads to an unbalanced Tur\'an proble...

Chang Liu · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.