Characterization of signed graphs with rank at most four using star complements

Abstract

The technique of star complements for a fixed graph eigenvalue μ, together with the associated notion of star sets, is a powerful method originally developed for constructing large unsigned graphs from smaller subgraphs. This approach has since been extended to signed graphs. In the latter setting, the values μ ∈ {1, 0, −1} pose certain obstacles to the general theory, as they permit the existence of infinite families of signed graphs sharing the same star complement for any of these eigenvalues. In this paper, we develop a refined extension of the star complement technique that accommodates these exceptional cases. As one application, we provide a complete characterization of all signed graphs with rank at most four, illustrating the broader potential of the extended technique.