Extremal Laplacian energy of C k + 1 → \overrightarrow{C_{k+1}} -free digraphs
Xiuwen Yang, Lin-Peng Zhang · 2026
Read Extremal Laplacian energy of C k + 1 → \overrightarrow{C_{k+1}} -free digraphs by Xiuwen Yang, Lin-Peng Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10953.txt.
Introduction
Xiuwen Yang and Lin-Peng Zhang carry Turán-type extremal problems to directed graphs, asking how large a digraph's Laplacian energy can be when a fixed directed cycle is forbidden. Laplacian energy here sums the squares of the Laplacian matrix's eigenvalues. For digraphs avoiding a directed cycle of a given length, they determine the maximum Laplacian energy exactly and characterize the digraphs that achieve it.
Catalog record
| CREATOR | Xiuwen Yang, Lin-Peng Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63172 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.10953
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extremal Laplacian energy of C k + 1 → \overrightarrow{C_{k+1}} -free digraphs Thanks: Supported by the Natural Science Foundation of Shaanxi Province (No. 2025JC-YBQN-108), the China Postdoctoral Science Foundation (No. 2025M783120), and Shandong Postdoctoral Science Foundation (No. SDZZ-ZR-202501340). Xiuwen Yang, Lin-Peng Zhang Abstract Abstract The Laplacian energy of a digraph G is defined as \sum_{i=1}^{n}\lambda_{i}^{2} , where \lambda_{i} are the eigenvalues of the Laplacian matrix of G . A (di)graph G is said to be H -free if it does not contain a copy of the fixed (di)graph H as a sub(di)graph. In this paper, we extend the Turán problems to spectral Turán problems in digraphs: what is the maximal Laplacian energy of an H -free digraph of given order? In particular, we determine the maximum Laplacian energy and characterize the extremal digraphs of \overrightarrow{C_{k+1}} -free digraphs. Key Words : spectral Turán problem; Laplacian energy; \overrightarrow{C_{k+1}} -free digraph AMS Subject Classification (2020) : 05C20, 05C35, 05C50 1 Introduction Before delving into essential terminology and notation, we first offer a brief introduction to establish the necessary background and motivation for our paper. 1.1 Background and motivation Our work is motivated by recent advances in extremal graph theory, particularly the rapidly growing field of spectral Turán problem. A (di)graph G is said to be H -free if it does not contain a copy of the fixed (di)graph H as a sub(di)graph. The Turán problem is a classical extremal problem in extremal graph theory that considers the maximum size of an H -free graph of given order. In 2010, Nikiforov [ 25 ] proposed a spectral Turán problem: what is the maximal spectral radius of a H -free graph of given order? This is also known as Brualdi-Solheid-Turán type problem. In early work, Wilf [ 29 ] investigated the problem of maximum spectral radius of K_{r+1} -free graphs of given order. Nikiforov [ 23 ] studied the maximum spectral radius problem for graphs forbidding odd cycles, while Nikiforov [ 25 ] further explored the case of forbidden paths. Furthermore, Nikiforov [ 25 ] proposed conjectures regarding the maximum spectral radius for graphs forbiddingcycles and trees. Recently, Cioabă et al. [ 4 ] determined the maximum spectral radius and the corresponding extremal graphs for graphs forbidding friendship graph. Zhai et al. [ 36 ] resolved the same problem for K_{2,r+1} -free graphs of given size. Later, Zhai and Lin [ 34 ] characterized the extremal graphs attaining the maximum spectral radius among graphs forbidding K_{s,t} -minors. Cioabă et al. [ 3 ] investigated the spectral extremal problem for graphs forbidding even cycles. More results on spectral Turán problems see [ 6 , 16 , 17 , 19 , 20 , 22 , 23 , 26 , 33 , 35 , 37 ] . But for digraphs, there are only a few results about spectral Turán problem. In [ 2 , 5 ] , Brualdi, Li and Drury determined the maximal spectral radius and extremal digraph of \overrightarrow{C_{2}} -free digraphs: if n is odd, the extremal digraph is a tournament which has indegree and outdegree \frac{n-1}{2} at each vertex; if n is even, the extremal digraph is a tournament which is isomorphic to the Brualdi-Li tournament. All the aforementioned results concern the spectral radius of adjacency matrices of graph. This leads to the natural extremal question: what is the maximal adjacency spectral radius of an H -free digraph of given order or size? However, the present work primarily investigates the Laplacian energy of digraphs. As is known, the classical Turán problem and its spectral analogue are intrinsically related for graphs. A natural question arises: does a similar relation hold for digraphs? While this is a compelling research direction, it remains largely unexplored. However, for the Laplacian energy of digraphs, which is fundamentally tied to the sum of squares of outdegrees (and thus to the arc count), a link to the digraph Turán problem appears more plausible. This possibility forms the primary motivation for our work: to investigate the spectral Turán problem for Laplacian energy by asking what is the maximum Laplacian energy of an H -free digraph with given order or size? Classic Turán problems form a cornerstone of extremal combinatorics, originating from Turán’s generalization of Mantel’s theorem. We recall the classic Turán theorem: for any integers n,k\geq 1 , the unique K_{k+1} -free graph on n vertices with the maximum number of edges is the Turán graph T_{n,k} —the complete k -partite graph with parts as equal as possible. More generally, for a given (di)graph H and n\in\mathbb{N}^{+} , we denote by \textnormal{ex}(n,H) the Turán number (the maximum number of edges/arcs in an H -free (di)graph of order n ), and by \textnormal{EX}(n,H) the family of all extremal (di)graphs attaining this bound. Theorem 1.1 . ( [ 14 ] ) Let k,n\in\mathbb{N}^{+} , n=qk+r , 0\leq r<k . Then \textnormal{ex}(n,K_{k+1})=\frac{k-1}{2k}n^{2}-\frac{r(k-r)}{2k}, and \textnormal{EX}(n,K_{k+1})=\{T_{n,k}\} . Although the Turán problem has been extensively studied for graphs, its extension to digraphs remains relatively unexplored. Brown and Harary [ 1 ] resolved Turán problems for complete digraphs \overleftrightarrow{K_{k+1}} and tournaments \overrightarrow{T_{k+1}} . Theorem 1.2 . ( [ 1 ] ) Let k,n\in\mathbb{N}^{+} . Then \textnormal{ex}(n,\overleftrightarrow{K_{k+1}})=\binom{n}{2}+\textnormal{ex}(n,K_{k+1})\ \ \textnormal{and}\ \ \textnormal{ex}(n,\overrightarrow{T_{k+1}})=2\textnormal{ex}(n,K_{k+1}). Howalla et al. [ 11 , 12 ] determined the maximum number of arcs in digraphs forbidding k directed paths with common endpoints for k=2,3 . Huang and Lyu [ 13 ] investigated Turán problems for oriented C_{4} with specific edge directions. Zhou and Li [ 32 ] characterized the maximum size and extremal digraphs for forbidden directed paths, directed cycles, and another variant of oriented C_{4} . As we discussed before, this work is devoted to investigating spectral Turán problems concerning Laplacian energy of \overrightarrow{C_{k+1}} -free digraphs. In 1970, Gutman [ 7 ] first introduced the energy of adjacency matrix of a graph as the sum of the absolute values of the eigenvalues. More recently, in 2006, Gutman and Zhou [ 10 ] defined the Laplacian energy of a graph as the sum of the absolute values of the differences between Laplacian eigenvalues and the average degree. In the same year, Lazić [ 15 ] defined the Laplacian energy of a graph as the sum of the squares of the Laplacian eigenvalues. In 2010, Perera and Mizoguchi [ 27 ] extended the Lazić version’s definition to digraphs. In 2015, Qi et al. [ 28 ] obtained lower and upper bounds on the Laplacian energy of digraphs and also characterized the extremal digraphs. In 2020, Yang and Wang [ 31 ] determined the directed trees, unicyclic digraphs and bicyclic digraphs which attain the maximal and minimal Laplacian energy among all digraphs with n vertices, respectively. In 2024, Yang et al. [ 30 ] characterized the digraphs which attain the minimal and maximal Laplacian energy within classes of digraphs with a fixed dichromatic number. We refer the interested reader to the three monographs [ 8 , 9 , 18 ] for a wide range of alternative definitions for energies of graphs and digraphs, and a wealth of references to obtained results. Before we present our results and proofs, we will recall some of the essential terminology and notation, and give some additional background and related results. 1.2 Terminology and notation For