Abstract
Let $G$ be a graph of order $n$ and $\mu$ be an adjacency eigenvalue of $G$ with multiplicity $k \geq 1$. A star complement $H$ for $\mu$ in $G$ is an induced subgraph of order $n-k$ with no eigenvalue $\mu$, and the vertex subset $X=V(G-H)$ is called a star set for $\mu$ in $G$. The study of star complements and star sets provides a strong link between graph structure and linear algebra. In this paper, we study the regular graphs with $K_{t,s}\ (s \geq t \geq 2)$ as a star complement for an eigenvalue $\mu$, especially, characterize the case of $t=3$ completely, obtain some properties when $t=s$, and propose some problems for further study.
Introduction: The Spectral-Structural Link
In the field of spectral graph theory, a fundamental objective is to understand how the eigenvalues of a graph's adjacency matrix reflect its underlying combinatorial structure. A particularly potent tool in this endeavor is the theory of star complements.
For a graph $G$ with an eigenvalue $\mu$ of multiplicity $k$, a star set $X$ is a set of $k$ vertices such that the induced subgraph $H = G - X$ does not have $\mu$ as an eigenvalue. This subgraph $H$ is known as the star complement for $\mu$. The significance of this relationship lies in the Reconstruction Theorem, which posits that the entire graph $G$ is uniquely determined by the star complement $H$, the eigenvalue $\mu$, and the connections between $X$ and $H$.
While previous literature has successfully characterized regular graphs where the star complement is a path, a cycle, or a small bipartite graph (specifically $K_{1,s}$ or $K_{2,s}$), this research extends the investigation to larger complete bipartite graphs $K_{t,s}$ where $s \ge t \ge 2$.
Methodology: Algebraic Reconstruction and Vertex Typing
The authors utilize a rigorous algebraic approach to "rebuild" $G$ from $K_{t,s}$. The core of this method involves categorizing vertices in the star set $X$ into specific "types." A vertex $u \in X$ is said to be of type $(a, b)$ if it is adjacent to $a$ vertices in the first partition of $K_{t,s}$ (of size $t$) and $b$ vertices in the second partition (of size $s$).
To determine which configurations are possible, the authors derive a system of compatibility equations. For any two vertices $u, v \in X$, their adjacency $a_{uv}$ and the inner product of their connection vectors must satisfy a bilinear form identity.
As shown in the table above, specific combinations of vertex types $(a, b)$ and $(c, d)$ yield fixed values for the adjacency $a_{uv}$ and the parameter $\rho_{uv}$. By solving these quadratic and cubic equations for integer solutions, the authors can systematically eliminate impossible graph structures and identify valid regular graphs.
Key Insights and Structural Constraints
The research yields several significant theoretical results regarding the interplay between regularity and spectral properties:
- The "Type" Identity: Every vertex in the star set must satisfy a strict algebraic identity (Equation 2.7 in the paper). This constraint is the primary filter that limits the possible connections between the star set and the complete bipartite star complement.
- Non-existence of $\mu = -t$: A major finding is the proof that no $r$-regular graph exists that has $K_{t,s}$ as a star complement for the eigenvalue $\mu = -t$.
- Symmetry in $K_{s,s}$: In cases where the star complement is a symmetric bipartite graph ($t=s$), the eigenvalue $\mu$ must be an integer, and its magnitude must be strictly less than $s$ ($|\mu| < s$).
- Multiplicity Bounds: The paper establishes a sharp upper bound for the multiplicity $k$ of the eigenvalue $\mu$: $k \le s(r-s)$. The authors demonstrate that this bound is reached only in highly specific configurations.
Characterization of the $t=3$ Case
A primary contribution of this work is the complete classification of regular graphs where $K_{3,s}$ is a star complement. The authors prove that for $K_{3,s}$, only four distinct scenarios can occur:
- The case where $\mu = -1$.
- The case where $\mu = \pm 4$, which leads to the complete bipartite graph $K_{4,4}$.
- A general class of $r$-regular graphs.
- The existence of three unique, non-isomorphic regular graphs ($G_1, G_2, G_3$) of orders 9, 12, and 15, which arise when $\mu=1$ and $s=3$.
Conclusion and Future Directions
While this paper provides a definitive answer for $t=3$, the general case for $t > 3$ remains an open area for research. The authors propose a challenge to the community to provide a general characterization for any $t$ and $s$ when vertex types are mixed. Furthermore, the structural commonalities between the discovered regular graphs suggest a deeper, perhaps more universal, pattern in spectral graph theory that warrants further investigation.
Summary updated