On Some Bi-Cayley Graphs over Cyclic Groups of Order $p^2 q^2$ and Related Extensions

This paper investigates the structural and combinatorial properties of Bi-Cayley graphs over cyclic groups of order $p^2q^2$, establishing that they are connected, biregular, have girth three and diameter five, while also extending these findings to arbitrary finite groups under specific conditions.

The Gist

Imagine you are an architect designing a massive, futuristic city. In the world of mathematics, this city is called a Bi-Cayley Graph.

Usually, mathematicians build cities based on a single set of rules (a "Cayley Graph"), where every building looks the same and connects to its neighbors in a predictable pattern. But in this paper, the authors decide to build a Bi-Cayley city. Think of this as building two identical twin cities sitting side-by-side, but with a twist: they are connected by a special bridge system that follows its own unique rules.

Here is a breakdown of what the authors discovered about these twin cities, using simple analogies.

1. The Blueprint: The Twin Cities

The authors focus on a specific type of city built on a grid of size $p^2q^2$ (where $p$ and $q$ are prime numbers, like 2, 3, 5, etc.).

• City A (The 0-side): This city follows Rule Set 1.
• City B (The 1-side): This city follows Rule Set 2.
• The Bridges: There are special bridges connecting a building in City A directly to its twin in City B.

The authors asked: If we build these cities with specific rules based on the "size" (order) of the connections, what does the whole structure look like?

2. The Big Discoveries

Is the City Connected? (Connectivity)

The Finding: Yes, you can get from any building to any other building.
The Analogy: Imagine you are stuck in City A. You can walk to your twin building in City B, walk around City B to a different spot, and walk back to City A. Because the "inner roads" of at least one of the cities are well-connected, the whole twin-city complex is one big, walkable neighborhood. You never get trapped in an isolated island.

How "Round" is the City? (Girth)

The Finding: The shortest loop you can walk is 3 steps long.
The Analogy: If you try to walk in a circle without backtracking, the smallest circle you can make involves 3 buildings. It's like a triangle. You can't make a square (4 steps) or a pentagon (5 steps) as the smallest loop; the triangle is the tightest turn possible. This happens because the rules for connecting buildings inside the cities naturally create these little triangles.

The "Party" Size (Clique Number)

The Finding: The biggest group of people where everyone knows everyone else is limited to the size of the larger prime number ($p$ or $q$).
The Analogy: Imagine a "secret handshake" party. You can only invite people who all know each other. The authors found that you can't have a massive party where everyone is friends. The largest possible party is limited by the size of the smaller "neighborhoods" within the city. If $p=3$ and $q=5$, the biggest party you can throw where everyone is friends is 5 people.

How Many Colors for the Map? (Chromatic Number)

The Finding: You need one more color than the size of the biggest party to paint the map so no two neighbors have the same color.
The Analogy: Imagine you are coloring a map of the city. You can't paint two connected buildings the same color. If the biggest "friend group" (clique) has 5 people, you need at least 5 colors. But because of the tricky way the two cities are linked, you actually need 6 colors (5 + 1) to make sure no two neighbors clash. It's like a puzzle where the two cities are fighting over the same color, forcing you to grab an extra crayon.

How Far is the Farthest Point? (Diameter)

The Finding: The longest walk you might ever have to take is 5 steps.
The Analogy: No matter where you start and where you want to go in this massive twin-city, you will never need to walk more than 5 blocks to get there. It's a surprisingly efficient city! Even though it's huge, the "shortcuts" provided by the bridges between the two cities keep everything close.

The "Lonely" Group (Independence Number)

The Finding: The largest group of people you can pick so that none of them know each other is quite large, but not quite double the size of the city.
The Analogy: Imagine trying to pick a group of people for a "silent retreat" where no two people know each other. You can pick a lot of people, but because the two cities are so tightly linked, you can't just pick everyone from City A and everyone from City B. There's some overlap and conflict. The authors calculated the exact maximum number of "loners" you can fit in the city.

3. The "What If" Scenario: Generalizing the Rules

The authors didn't just stop at this specific city design. They asked: "Does this work for any city, not just this specific grid?"

They found that many of these rules hold true even if you change the blueprint to a completely different type of group, as long as the "bridges" (the connection set) follow certain logic.

• The Twist: They even looked at a scenario where the bridges are made of "involutions" (elements that are their own opposites, like a mirror reflection).
• The Result: When you use these special "mirror bridges," the rules for how big a "party" (clique) can be get a little more complicated, but the core idea remains: the structure of the city is dictated by the rules of the bridges.

Summary

In plain English, this paper is about mapping the geometry of a specific type of mathematical network.

The authors took a complex algebraic structure (a group of order $p^2q^2$), split it into two halves, and connected them. They then measured the city's properties:

• Is it all in one piece? Yes.
• How small are the loops? Triangles (3).
• How big is the biggest friend group? Limited by the prime numbers.
• How many colors do we need? One more than the friend group size.
• How far is the farthest walk? Only 5 steps.

They proved that even though the math is heavy, the resulting "city" is surprisingly compact, efficient, and follows a very predictable pattern. They also showed that these patterns aren't just a fluke of this specific city; they apply to many other mathematical structures too.

Technical Summary

Here is a detailed technical summary of the paper "On Some Bi-Cayley Graphs over Cyclic Groups of Order $p^2q^2$ and Related Extensions" by Atmaja, Susanti, and Erfanian.

1. Problem Statement

The paper investigates the structural and combinatorial properties of Bi-Cayley graphs defined over cyclic groups of order $n = p^2q^2$, where $p$ and $q$ are distinct primes. While Cayley graphs (encoding a single group $G$ via a connection set $S$) are well-studied, Bi-Cayley graphs generalize this by utilizing two disjoint copies of a group ($\{0\} \times G$ and $\{1\} \times G$) and three connection sets ($S_1, S_2, S_3$).

The specific problem addressed is the determination of fundamental graph invariants for Bi-Cayley graphs where the connection sets are defined by the orders of group elements. Specifically:

• $S_1 = \{x \in G : |x| = p \text{ or } q\}$
• $S_2 = \{x \in G : |x| = p^2 \text{ or } q^2\}$
• $S_3 = \{e_G\}$ (the identity element)

The authors aim to explicitly calculate connectivity, regularity, girth, clique number, chromatic number, diameter, and independence number, and then extend these findings to arbitrary finite groups under specific constraints.

2. Methodology

The authors employ a combination of group-theoretic decomposition and combinatorial graph analysis:

• Group Decomposition: They utilize the isomorphism $\mathbb{Z}_{p^2q^2} \cong \mathbb{Z}_{p^2} \times \mathbb{Z}_{q^2}$. This allows them to analyze adjacency conditions component-wise, treating group elements as ordered pairs $(g_p, g_q)$.
• Subgraph Analysis: The Bi-Cayley graph $\Gamma$ is decomposed into two induced Cayley subgraphs:
  • $\Gamma_0 = \text{Cay}(G, S_1)$ (the "0-side")
  • $\Gamma_1 = \text{Cay}(G, S_2)$ (the "1-side")
  • The interaction between sides is governed by $S_3$.
• Cartesian Product Isomorphism: For the analysis of $\Gamma_1$, the authors prove it is isomorphic to the Cartesian product of two complete multipartite graphs ($K_{p,\dots,p} \square K_{q,\dots,q}$). This structural insight is crucial for calculating chromatic and independence numbers.
• Extremal Combinatorics: The determination of independence numbers and clique numbers involves constructing specific subsets of vertices and applying the Pigeonhole Principle to prove maximality or bounds.
• Generalization: The methodology extends from the specific cyclic case to arbitrary finite groups by analyzing the properties of generating sets and involutions (elements of order 2).

3. Key Contributions and Results

A. Structural Properties for Cyclic Groups ($G = \mathbb{Z}_{p^2q^2}$)

1. Connectivity and Regularity:

   • The graph $\Gamma$ is connected.
   • It is biregular: Vertices in the 0-side have degree $p(p-1) + q(q-1) + 1$, while vertices in the 1-side have degree $p+q-1$.
   • The graph is not Eulerian because the degrees are odd (for distinct primes $p, q$).

2. Girth:

   • The girth (length of the shortest cycle) is 3. The authors prove that no 3-cycles can cross between the two sides; they must exist entirely within $\Gamma_0$ or $\Gamma_1$.

3. Clique Number ($\omega(\Gamma)$):

   • The clique number is $\max\{p, q\}$.
   • Any clique of size $>2$ must reside entirely within one side ($\Gamma_0$ or $\Gamma_1$) because $S_3$ only connects $(0, g)$ to $(1, g)$, preventing larger cliques from spanning both sides.

4. Chromatic Number ($\chi(\Gamma)$):

   • The chromatic number is $\max\{p, q\} + 1$.
   • While the subgraphs $\Gamma_0$ and $\Gamma_1$ can be colored with $\max\{p, q\}$ colors, the "cross-edges" (connecting $(0,g)$ to $(1,g)$) create conflicts that necessitate one additional color.

5. Diameter ($\text{diam}(\Gamma)$):

   • The diameter is 5.
   • The analysis shows that while distances within $\Gamma_1$ are at most 4, and within components of $\Gamma_0$ are at most 2, the maximum distance between vertices in different components of $\Gamma_0$ (requiring a path through $\Gamma_1$) reaches 5.

6. Independence Number ($\alpha(\Gamma)$):

   • The independence number is $2pq \min{p, q} - \min{p^2, q^2}$.
   • This result accounts for the overlapping structure of maximum independent sets in $\Gamma_0$ and $\Gamma_1$. The authors show that one cannot simply sum the independence numbers of the two subgraphs due to vertex overlaps in the optimal construction.

B. Extensions to Arbitrary Finite Groups

The paper generalizes several results to Bi-Cayley graphs over any finite group $G$ with connection sets $S_1, S_2$ and $S_3 = \{e_G\}$:

• Connectivity: $\Gamma$ is connected if and only if at least one of $S_1$ or $S_2$ generates $G$.
• Clique Number: $\omega(\Gamma) = \max\{\omega(\Gamma_0), \omega(\Gamma_1), 2\}$.
• Chromatic Number Bounds: $\max\{\chi(\Gamma_0), \chi(\Gamma_1)\} \leq \chi(\Gamma) \leq 1 + \max\{\chi(\Gamma_0), \chi(\Gamma_1)\}$.

C. Special Case: Involutions in $S_3$

The authors explore a variation where $S_3$ is the set of all involutions ($I(G)$) of the group.

• This creates a "cross-edges subgraph" ($\Gamma_{ce}$) that is $|I(G)|$-regular.
• If $G$ is generated by its involutions, the entire Bi-Cayley graph is connected regardless of $S_1$ and $S_2$.
• They introduce the concept of mixed cliques (spanning both sides) and provide bounds on their size under "involution-separating" conditions.

4. Significance

• Bridging Algebra and Combinatorics: The paper demonstrates how specific algebraic constraints (element orders) translate into precise combinatorial invariants (diameter, chromatic number) in graph theory.
• Refinement of Bi-Cayley Theory: While Bi-Cayley graphs are a known generalization of Cayley graphs, this work provides the first explicit, detailed calculation of all major invariants for a non-trivial class of groups ($p^2q^2$) with order-based connection sets.
• Structural Insight: The decomposition of the problem into two interacting Cayley subgraphs offers a robust framework for analyzing complex graph structures. The finding that the diameter is exactly 5 and the chromatic number is $\max\{p,q\}+1$ provides concrete benchmarks for future research.
• Generalizability: By extending results to arbitrary finite groups and exploring the role of involutions, the paper moves beyond cyclic groups, offering a broader theoretical foundation for the study of Bi-Cayley graphs in symmetric and non-abelian contexts.

In summary, this paper provides a comprehensive algebraic characterization of a specific family of Bi-Cayley graphs, establishing exact formulas for their key parameters and laying the groundwork for analyzing similar structures in more general group-theoretic settings.