Core and Corona in 2-Bicritical Odd-Bicyclic Graphs

This paper provides a complete structural classification of 2-bicritical odd-bicyclic graphs into four families using ear-pendant decompositions, explicitly computing their maximum independent sets, cores, and coronas to establish precise relationships between these parameters and the relative positions of the graphs' odd cycles.

The Gist

Imagine a graph as a city made of intersections (vertices) and roads (edges). In this city, we are looking for the "Safe Zones": groups of intersections where no two are directly connected by a road. If you pick a Safe Zone, you can't walk directly from one spot in the group to another without leaving the group.

The paper explores a specific type of city called a 2-bicritical graph. Think of these as cities that are incredibly "socially active." In a 2-bicritical city, if you try to gather any group of people (an independent set) who don't know each other, the number of their neighbors is always strictly greater than the size of the group itself. It's a city where everyone has too many friends outside their immediate circle.

The researchers focus on cities that have a very specific architectural quirk: they contain at most two "loops" of odd length (like a triangle, a pentagon, or a heptagon). Most cities are either perfectly balanced (bipartite) or have just one weird loop. These cities have two, which makes their structure much more interesting and complex.

The Two Big Concepts: The "Core" and the "Corona"

To understand the paper, we need two main characters:

1. The Core (The "Must-Haves"): Imagine you have a list of every possible "perfect" Safe Zone in the city. The Core is the intersection of all these lists. It contains only the intersections that appear in every single perfect Safe Zone.

   • Analogy: If you were planning a party and needed to pick a group of guests who don't know each other, the Core is the list of people who must be invited, no matter how you arrange the party. They are the essential, non-negotiable members.

2. The Corona (The "Maybe-Haves"): This is the union of all those lists. It contains every intersection that appears in at least one perfect Safe Zone.

   • Analogy: The Corona is the list of everyone who could be invited. If there is even one way to organize the party where this person fits in, they are on the Corona list.

The paper asks a simple but deep question: How big are these lists? Specifically, if you add the number of people in the "Must-Have" list (Core) to the number of people in the "Maybe-Have" list (Corona), what do you get?

The Four Types of Cities

The authors discovered that all these 2-bicritical cities with two odd loops fall into four distinct architectural families. The relationship between the Core and the Corona depends entirely on which family the city belongs to:

1. The "One-Loop" City (One-odd cycle)

This is a city that only has one odd loop. It's the simplest case.

• The Result: The Core and Corona are perfectly balanced.
• The Math: Core + Corona = 2 × (Max Safe Zone Size).
• The Metaphor: It's like a perfectly symmetrical seesaw. The essential people and the optional people fit together to fill exactly twice the space of the largest possible group.

2. The "Fused" City (Fused-odd)

Here, the two odd loops are glued together, sharing at least two intersections. Imagine two triangles sharing an edge.

• The Result: The Core is empty (no one is essential), but the Corona is huge (almost everyone is optional).
• The Math: Core + Corona = 2 × (Max Safe Zone Size) + 1.
• The Metaphor: Because the loops are fused, the city is so flexible that no single person is required for every arrangement. However, the "fused" nature adds a tiny bit of extra "wiggle room," making the total count of potential guests slightly higher than the balanced case.

3. The "Even-Linked" City (Even-linked)

The two loops are connected by a bridge (path) that has an even number of steps.

• The Result: Similar to the One-Loop city, the numbers balance out perfectly.
• The Math: Core + Corona = 2 × (Max Safe Zone Size).
• The Metaphor: The even bridge acts like a perfect translator between the two loops, keeping the system in perfect equilibrium. The "Must-Haves" and "Maybe-Haves" sum up to a clean, even number.

4. The "Odd-Linked" City (Odd-linked)

The two loops are connected by a bridge with an odd number of steps.

• The Result: This is the most chaotic case. The Core is empty (no one is essential), and the Corona includes everyone in the city.
• The Math: Core + Corona = 2 × (Max Safe Zone Size).
• The Metaphor: The odd bridge creates a "flip-flop" effect. Depending on how you arrange the party, you might need to swap the entire group of people from one side of the bridge to the other. Because of this total flexibility, everyone is a "Maybe-Have," and no one is a "Must-Have."

The Big Discovery

The paper proves a beautiful rule about these cities:

• If the two loops are far apart (connected by an even bridge) or separate, the sum of the Core and Corona is exactly twice the size of the largest group.
• If the two loops are glued together (sharing two or more points), the sum is twice the size plus one.
• If the city is disconnected (two separate loops with no bridge), the sum is twice the size plus two.

Why Does This Matter?

This research is like finding a new law of physics for graph theory. Previously, mathematicians understood these rules for simple, balanced cities (bipartite graphs) or cities with just one weird loop. This paper extends that understanding to cities with two loops, which are much more complex and "non-König–Egerváry" (a fancy way of saying they don't follow the simple, standard rules).

By classifying these graphs into four families, the authors have created a "map" that allows mathematicians to predict the behavior of these complex structures just by looking at how the loops are connected. It turns a messy, chaotic problem into a neat, organized system of four categories.

In short: The paper shows that even in a complex city with two weird loops, the rules of "who must be invited" and "who can be invited" follow a strict, predictable pattern based entirely on how those loops are connected.

Technical Summary

Here is a detailed technical summary of the paper "Core and Corona in 2-Bicritical Odd-Bicyclic Graphs" by Kevin Pereyra.

1. Problem Statement and Context

The paper investigates the structural properties of maximum independent sets in a specific class of graphs: 2-bicritical graphs containing at most two odd cycles.

• Key Definitions:

  • Core($G$): The intersection of all maximum independent sets of $G$.
  • Corona($G$): The union of all maximum independent sets of $G$.
  • 2-Bicritical Graph: A graph $G$ where $|N(S)| > |S|$ for every non-empty independent set $S$. This class is structurally dual to König–Egerváry graphs (where $\alpha(G) + \mu(G) = |V(G)|$). Pulleyblank (1979) showed that almost all graphs are 2-bicritical.
  • Odd-Bicyclic: A graph containing at most two odd cycles.

• Motivation:

  • For König–Egerváry graphs (including bipartite graphs), it is known that $|corona(G)| + |core(G)| = 2\alpha(G)$.
  • For almost bipartite non-König–Egerváry graphs (graphs with exactly one odd cycle), the sum is $2\alpha(G) + 1$.
  • The paper addresses Problem 1.3: Characterize graphs where $|corona(G)| + |core(G)| = 2\alpha(G) + 1$ and extend these results to graphs with two odd cycles, a regime where the behavior of independent sets becomes qualitatively more complex.

2. Methodology

The author employs a combination of structural graph theory and decomposition techniques:

• Ear-Pendant Decomposition: The primary tool used to classify 2-bicritical graphs. A connected graph is 2-bicritical if and only if it admits an ear-pendant decomposition (starting from an odd cycle or an odd homeomorph of $K_4$).
• Classification Strategy: The paper classifies 2-bicritical graphs with at most two odd cycles into four distinct families based on how the odd cycles are connected:
  1. One-odd cycle graphs: Graphs with a single odd cycle.
  2. Fused-odd graphs: Two odd cycles sharing at least one vertex (formed by adding an odd ear to the first cycle).
  3. Even-linked graphs: Two odd cycles connected by a path of even length.
  4. Odd-linked graphs: Two odd cycles connected by a path of odd length.
• Gallai–Edmonds Structure Theorem: Used to analyze the matching structure ($D(G), A(G), C(G)$) and relate it to the independence number.
• Bipartite Matching-Covered Graphs: For linked graphs, the author constructs auxiliary bipartite graphs by removing specific vertices from the odd cycles to apply Lovász's ear decomposition theorems for matching-covered graphs.

3. Key Contributions and Results

The paper provides explicit formulas for $\alpha(G)$, $core(G)$, and $corona(G)$ for each of the four families and establishes the relationship between the sum of the sizes of the core and corona and the independence number.

A. Classification and Structural Analysis

• One-odd cycle & Fused-odd: These are factor-critical.
  • If the cycles share $\ge 2$ vertices (fused-odd), $core(G) = \emptyset$ and $corona(G) = V(G)$.
  • If they share exactly 1 vertex, $corona(G) = V(G) \setminus \{x\}$ where $x$ is the unique articulation point.
  • Result: $|core(G)| + |corona(G)| = 2\alpha(G) + 1$.
• Even-linked Graphs:
  • The graph behaves similarly to bipartite matching-covered graphs.
  • $core(G)$ corresponds to one partition set of the underlying bipartite structure (excluding specific cycle vertices).
  • $corona(G)$ is the complement of the other partition set.
  • Result: $|core(G)| + |corona(G)| = 2\alpha(G)$.
• Odd-linked Graphs:
  • These graphs possess a perfect matching.
  • $core(G) = \emptyset$ and $corona(G) = V(G)$.
  • Result: $|core(G)| + |corona(G)| = 2\alpha(G)$.

B. Main Theorems

Theorem 7.1 (Sum Characterization):
For a 2-bicritical graph $G$ with two odd cycles:

1. If $G$ is connected and the cycles share at most one vertex (including even-linked, odd-linked, and single-vertex fused cases):
   $$|core(G)| + |corona(G)| = 2\alpha(G)$$
2. If the cycles share at least two vertices (fused-odd with overlap):
   $$|core(G)| + |corona(G)| = 2\alpha(G) + 1$$
3. If $G$ is disconnected (two separate odd cycles):
   $$|core(G)| + |corona(G)| = 2\alpha(G) + 2$$

Theorem 7.2 (Partition Property):
For a connected 2-bicritical graph with at most two odd cycles, $corona(G) \cup N(core(G)) = V(G)$ if and only if the two odd cycles do not share at least two vertices.

Theorem 7.3 (Matching Number Relation):

• If $G$ is connected: $\alpha(G) + \mu(G) = n - 1$.
• If $G$ is disconnected: $\alpha(G) + \mu(G) = n - 2$.

4. Significance and Impact

• Extension of Theory: The work successfully extends the theory of core and corona from König–Egerváry graphs and almost bipartite graphs to the broader, non-König–Egerváry setting of 2-bicritical graphs.
• Structural Characterization: It provides a complete, purely structural characterization of when the sum $|core(G)| + |corona(G)|$ deviates from $2\alpha(G)$. The deviation is strictly determined by the relative position of the odd cycles (specifically, whether they share two or more vertices).
• Algorithmic Implications: The paper suggests (Conjecture 7.4) that computing core and corona for these graphs is polynomial, and the explicit structural formulas derived here serve as a foundation for such algorithms.
• Open Problems: The paper concludes by posing problems for graphs with $k \ge 3$ odd cycles, suggesting that the complexity of the core/corona structure increases significantly with the number of odd cycles.

Summary Conclusion

This paper resolves the structural behavior of maximum independent sets in 2-bicritical graphs with up to two odd cycles. By utilizing ear-pendant decompositions, the author demonstrates that the "rigidity" of the core and corona depends entirely on the connectivity of the odd cycles. The results unify previous findings on bipartite and almost bipartite graphs, showing that the presence of a second odd cycle introduces a dichotomy: if the cycles are "fused" heavily (sharing $\ge 2$ vertices), the graph behaves like the almost bipartite case ($+1$ deviation); otherwise, it behaves like a bipartite-like structure ($0$ deviation).