Extremal Laplacian energy of $\overrightarrow{C_{k+1}}$-free digraphs

This paper extends Turán problems to the spectral domain of digraphs by determining the maximum Laplacian energy and characterizing the extremal digraphs for the class of $\overrightarrow{C_{k+1}}$-free digraphs.

The Gist

Imagine you are the mayor of a bustling city called Graph City. In this city, the buildings are vertices (people or places), and the one-way streets connecting them are arcs (directed edges).

Your job is to design the most "energetic" city possible, but you have a strict rule: No loops longer than a certain size are allowed. Specifically, you cannot build a round-trip route that visits $k+1$ distinct buildings and returns to the start without repeating any stops. This is called being $C_{k+1}$-free.

The paper you asked about is a mathematical detective story about finding the most energetic city under this rule. Here is the breakdown in simple terms:

1. What is "Laplacian Energy"?

In the world of Graph City, "energy" isn't about electricity; it's about traffic flow.

• Every building has an outdegree: the number of streets leaving that building.
• The Laplacian Energy is a score calculated by squaring the number of outgoing streets for every building and adding them all up.
• The Analogy: Think of it like a "hustle score." If a building has 1 street leaving, its score is $1^2 = 1$. If it has 10 streets leaving, its score is$10^2 = 100$. The city with the highest total hustle score is the winner.

Why square the numbers? Because in math, squaring a number makes big numbers much bigger. A city with one super-hub (a building with 100 streets) will have a much higher energy score than a city where everyone has 10 streets, even if the total number of streets is the same. The paper wants to find the layout that maximizes this "super-hub" effect.

2. The Rule: No Big Loops

The city council says: "You can build as many streets as you want, but you cannot create a loop that visits $k+1$ specific buildings in a circle."

• If $k=1$, you can't have a loop of 2 buildings (A $\to$ B $\to$ A). This means you can't have two-way streets between any pair. The city must be a Tournament (like a rock-paper-scissors tournament where every pair plays once, and someone always wins).
• If $k=2$, you can't have a loop of 3 buildings (A $\to$ B $\to$ C $\to$ A).
• If $k$ is large, you just can't have very long loops.

3. The Big Question

The mathematicians asked: "What does the most energetic city look like if we follow these rules?"

They discovered that the answer depends on how many buildings ($n$) you have and the size of the forbidden loop ($k$).

The Winning Blueprint: The "Layered Pyramid"

The most energetic city isn't a random mess. It looks like a perfectly organized pyramid of layers:

1. The Layers: You divide the city into groups (layers).
2. The Flow: Every building in Layer 1 sends streets to everyone in Layer 2. Every building in Layer 2 sends streets to everyone in Layer 3, and so on.
3. The Clusters: Inside each layer, the buildings are fully connected to each other (like a mini-party where everyone knows everyone).
4. The Size: The layers are almost equal in size. If you have a few extra buildings left over, they form a slightly smaller final layer.

This structure is called the Turán Digraph (specifically $\vec{F}_{n,k}$). It's the mathematical equivalent of stacking blocks perfectly to reach the highest point without toppling over.

4. The Special Cases (The Plot Twists)

The paper breaks the problem into three scenarios, like different levels in a video game:

• Level 1 ($k=1$): The "No Two-Way Streets" Rule.

  • The Winner: A Transitive Tournament. Imagine a strict hierarchy: The Mayor beats everyone, the Vice-Mayor beats everyone except the Mayor, and so on. There is a clear "King of the Hill."
  • Why? This creates the biggest possible difference in "outgoing streets" between the top and bottom, maximizing the energy score.

• Level 2 ($k=2$): The "No 3-Building Loops" Rule.

  • The Winner: This is tricky! The city looks like a series of balanced pairs. Imagine couples (A and B) where A and B have streets going both ways between them, but A and B only send streets out to the next couple.
  • The Twist: If the total number of buildings is odd, the last group might be a trio or a single person. The paper proves that these specific "pairing" structures are the most energetic.

• Level 3 ($k \ge 3$): The "No Long Loops" Rule.

  • The Winner: Back to the Layered Pyramid. The "pairing" trick doesn't work here. The best strategy is simply to make the layers as equal as possible and push all the traffic forward.
  • The Result: The paper provides a precise formula (a recipe) to calculate the exact energy score for any city size $n$ and rule $k$.

5. How Did They Solve It? (The Detective Work)

The authors didn't just guess. They used a powerful mathematical tool called Karamata's Inequality.

• The Metaphor: Imagine you have a pile of gold coins (the total number of streets). You want to distribute them among the buildings to get the highest "squared" score.
• The Logic: Karamata's inequality says that to get the highest score, you should make the distribution as uneven as possible. You want a few buildings with huge numbers of streets and many with few.
• The Proof: They showed that if you try to rearrange the streets to make the distribution more even, you either break the "no loop" rule or you lose energy. If you try to make it more uneven, you inevitably create a forbidden loop. The "Layered Pyramid" is the perfect balance point where you are as uneven as possible without breaking the rules.

Summary

This paper answers a fundamental question in network theory: How do you organize a network to maximize its "flow energy" while preventing long cycles?

The answer is surprisingly structured:

1. Organize into layers.
2. Push traffic forward from layer to layer.
3. Keep layers equal in size.
4. Fill the layers with internal connections.

It's like organizing a relay race where the baton always moves forward, and the runners in the front leg run as fast as possible, ensuring the whole team achieves the maximum possible speed without anyone running in circles.

Technical Summary

Here is a detailed technical summary of the paper "Extremal Laplacian energy of $\overrightarrow{C}_{k+1}$-free digraphs."

1. Problem Statement

The paper addresses a Spectral Turán problem in the context of directed graphs (digraphs). While classical Turán problems seek the maximum number of edges in a graph forbidding a specific subgraph $H$, and spectral Turán problems typically focus on the maximum spectral radius of the adjacency matrix, this work investigates the Laplacian energy of $H$-free digraphs.

Specifically, the authors aim to determine:

1. The maximum Laplacian energy ($LE$) of a digraph of order $n$ that does not contain a directed cycle of length $k+1$ (denoted as $\overrightarrow{C}_{k+1}$-free).
2. The structural characterization of the extremal digraphs that achieve this maximum energy.

The Laplacian energy for a digraph $G$ is defined as the sum of the squares of the eigenvalues of its Laplacian matrix $L(G) = D^+(G) - A(G)$, where $D^+$ is the diagonal outdegree matrix and $A$ is the adjacency matrix. A key formula utilized is:
$$LE(G) = \sum_{i=1}^n (d^+_i)^2 + c_2$$
where $d^+_i$ are the outdegrees of the vertices and $c_2$ is the number of directed closed walks of length 2.

2. Methodology

The authors employ a combination of extremal graph theory, spectral graph theory, and inequality analysis. The core methodological pillars include:

• Turán Number Utilization: The paper builds upon existing results by Zhou and Li (2023) regarding the Turán number $ex(n, \overrightarrow{C}_{k+1})$ and the structure of extremal digraphs for arc count. The authors hypothesize that the digraph maximizing Laplacian energy shares the same structural family as the one maximizing the number of arcs.
• Karamata's Inequality: This is the primary analytical tool. Since $LE(G)$ depends heavily on the sum of squared outdegrees ($\sum (d^+_i)^2$), the authors use Karamata's inequality to show that a sequence of outdegrees that is "more spread out" (majorizes another sequence) yields a higher sum of squares. They prove that the extremal digraphs have outdegree sequences that majorize any other valid $\overrightarrow{C}_{k+1}$-free digraph.
• Arc Transformation and Structural Analysis:
  • The authors perform "arc transformations" (deleting an arc $(u, v)$ and adding $(x, y)$) to compare a candidate extremal graph against others.
  • They analyze how these transformations affect both the First Zagreb Index ($M_1 = \sum (d^+_i)^2$) and the term $c_2$ (closed walks of length 2).
  • They demonstrate that any deviation from the proposed extremal structure either reduces the sum of squared outdegrees or introduces a forbidden $\overrightarrow{C}_{k+1}$ cycle.
• Case Separation: The proofs are divided based on the value of $k$:
  • Case $k=1$: Forbidden $\overrightarrow{C}_2$ (2-cycles).
  • Case $k=2$: Forbidden $\overrightarrow{C}_3$ (3-cycles).
  • Case $k \geq 3$: Forbidden $\overrightarrow{C}_{k+1}$.

3. Key Contributions and Results

The paper provides exact formulas for the maximum Laplacian energy and characterizes the extremal digraphs for all $k \geq 1$.

A. Case $k=1$ (Forbidden $\overrightarrow{C}_2$)

• Context: A $\overrightarrow{C}_2$-free digraph is a tournament.
• Result: The maximum Laplacian energy is achieved by the transitive tournament.
• Formula:
  $$exLE(n, \overrightarrow{C}_2) = \frac{n(n-1)(2n-1)}{6}$$
• Structure: The outdegree sequence is $\{n-1, n-2, \dots, 1, 0\}$.

B. Case $k=2$ (Forbidden $\overrightarrow{C}_3$)

• Context: This is more complex because the structure maximizing arcs (extremal for Turán number) is not unique in terms of Laplacian energy; the internal structure of the parts matters.
• Result: The extremal digraphs belong to a class denoted as $\overrightarrow{BK}_{n,p}$, which consists of a sequence of parts where each part induces a balanced complete bipartite digraph, and parts are ordered such that all arcs go from earlier parts to later parts.
• Distinction:
  • If $n$ is even ($r=0$), the extremal graph is $\overrightarrow{BK}^0_{n,p}$ (all parts have even size).
  • If $n$ is odd ($r=1$), the extremal graph is $\overrightarrow{BK}^1_{n,p}$ (one part has odd size, others even).
• Formula:
  $$exLE(n, \overrightarrow{C}_3) = \frac{2q}{3}(3n^2 - 6qn + 4q^2 + 2)$$
  where $n = 2q + r$.

C. Case $k \geq 3$ (Forbidden $\overrightarrow{C}_{k+1}$)

• Context: For $k \geq 3$, the extremal structure for arc count is a specific family of digraphs $\overrightarrow{F}_{n,k}$, consisting of $q$ copies of a complete digraph $\overleftrightarrow{K}_k$ and one copy of $\overleftrightarrow{K}_r$ (if $r>0$), arranged in a transitive order.
• Result: The authors prove that within the family $\overrightarrow{F}_{n,k}$, the Laplacian energy is maximized when the smaller complete subgraph ($\overleftrightarrow{K}_r$) is placed at the end of the transitive chain (i.e., in the last partition).
• Structure:
  • If $r=0$: The unique extremal graph is $\overrightarrow{F}^0_{n,k}$ (all parts size $k$).
  • If $0 < r < k$: The unique extremal graph is$\overrightarrow{F}^{q+1}{n,k}$(the part of size$r$is the last one,$V{q+1}$).
• Formula:
  $$exLE(n, \overrightarrow{C}_{k+1}) = \frac{1}{3}n^3 + \left(\frac{k}{2}-1\right)n^2 + \frac{k^2}{6}n + \frac{2}{3}r^3 - \frac{k}{2}r^2 - \frac{k^2}{6}r$$

4. Significance and Implications

1. Extension of Spectral Turán Theory: This work successfully extends the spectral Turán problem from the adjacency spectral radius to Laplacian energy in the domain of digraphs, a relatively unexplored area compared to undirected graphs.
2. Relationship between Arc Count and Energy: The paper establishes a strong link between the number of arcs and Laplacian energy. In most cases ($k=1$ and $k \geq 3$), the digraph with the maximum number of arcs also maximizes the Laplacian energy. However, for $k=2$, the paper reveals that while the family of extremal graphs is the same as the Turán extremal family, the specific internal structure (balanced bipartite vs. complete) and the placement of the remainder part are critical for maximizing energy.
3. Methodological Advancement: The rigorous application of Karamata's inequality to outdegree sequences in the context of forbidden directed cycles provides a robust framework for future spectral extremal problems.
4. Open Problems: The authors identify that the extremal digraphs for maximum Laplacian energy and maximum adjacency spectral radius are not always the same (as seen in the $k=1$ case where transitive tournaments maximize energy but Brualdi-Li tournaments maximize spectral radius). They propose open problems regarding the characterization of extremal digraphs for forbidden paths ($\overrightarrow{P}_{k+1}$) and the relationship between these different spectral measures.

In summary, the paper provides a complete solution to the spectral Turán problem for Laplacian energy in $\overrightarrow{C}_{k+1}$-free digraphs, offering precise formulas and structural characterizations that deepen the understanding of the interplay between graph topology, arc distribution, and spectral properties in directed graphs.