Abstract
This paper consists of a few results, discovered and proved during the 2012-2013 research group at Eastern Oregon University. Inertia tables are a visual representation of the possible inertias of a given graph. The inertia of a graph counts the number of real positive and negative eigenvalues of its corresponding adjacency matrix. The problem of studying inertia tables is directly related to the inverse eigenvalue problem and can be used as a tool for the minimum rank problem. This paper describes the inverse eigenvalue problem, and tools used. We describe a number of new general formulas for various simple undirected graphs and improved upon an established notation for inertia tables.
Introduction
In spectral graph theory, the inverse eigenvalue problem seeks to determine the possible eigenvalues for all real symmetric matrices associated with a specific graph structure. Due to the complexity of this problem, researchers often pivot to the inverse inertia problem. Instead of exact values, this approach focuses on the inertia of a graph—a triple $(\pi, \nu, \delta)$ representing the count of positive, negative, and zero eigenvalues, respectively.
Determining the inertia set of a graph is a critical step in solving the minimum rank problem, which identifies the smallest possible rank among all matrices associated with a graph. While inertia sets for simple graphs like paths ($P_n$) and cycles ($C_n$) are well-documented, complex graph families require more sophisticated analytical tools.
Methodology
The research utilizes a combination of combinatorial graph theory and linear algebra, centered on three primary pillars:
- Refined T-Notation: The authors introduced $T^k_{[m,n]}$, where $m$ is the minimum rank, $n$ is the maximum rank, and $k$ denotes an "inset" from the axes. This notation efficiently describes "bumps"—regions in the inertia set where the minimum rank is detached from the axes.
- Cut-Vertex Theorem: Theorem 4.3 serves as the primary analytical engine. It allows the inertia of a composite graph (formed by joining two graphs at a single vertex) to be calculated from the inertias of its individual components and their vertex-deleted subgraphs.
- Inductive Proofs: Formulas for complex structures are built inductively from basic building blocks. This includes generalized stars (paths joined at a center), bouquets (cycles joined at a center), and supernovas (combinations of stars and bouquets).
Theoretical Framework and Notation
A key contribution of this work is the visualization and formalization of inertia tables. These tables are not always simple trapezoids; they often exhibit "bumps" where certain low-rank inertias require a specific balance of positive and negative eigenvalues.
By refining the $T^k_{[m,n]}$ notation, the authors transformed the tedious pointwise addition of coordinate sets into manageable algebraic operations. This algebraic composition demonstrates that the inertia of a complex graph is essentially the union of the inertias of its constituent parts under specific rules.
Results for Graph Families
The paper successfully characterizes the inertia sets for several sophisticated graph families:
- Supernovas: The authors defined the inertia for graphs containing $\alpha$ cycles and $\beta$ pendant paths.
- Pulsars and Binary Stars: The research derived a four-part union formula for pulsars—graphs consisting of two supernovas joined by a cycle. Similarly, formulas were provided for binary stars (two supernovas joined by a path), with distinctions made based on the length of the connecting path ($w=2$ vs. $w>2$).
- Complete Bipartite Joins: It was proven that for a graph $G$ formed by joining two complete bipartite graphs $K_{a,b}$ and $K_{c,d}$ at a vertex, the minimum rank $mr(G)$ never exceeds 4.
Conclusion
While the authors successfully modeled "bumps" (protrusions in the inertia set), they identified a structural curiosity termed "indents." These are hypothetical "holes" in the middle of the minimum rank line that still touch the axes. The existence of graphs with such inertia sets remains an open question. Future work may extend these specific family formulas to more arbitrary graph topologies.
Summary updated