On minimum rank of graphs with given dominating induced subgraphs

Abstract

An induced subgraph of a graph G is said to be dominating if every vertex of G is at distance at most one from this subgraph. We investigate pairs (G, F ) where F is a nonsingular dominating induced subgraph of G, and the rank of G (that is, the rank of its adjacency matrix) attains the minimum, i.e., equals the number of vertices in F . It turns out that the inverse of the adjacency matrix of a nonsingular path, half graph, or even cycle is the adjacency matrix of a related signed graph; here, a half graph refers to a connected chain graph with exactly one vertex in each cell. We exploit this property to give a complete characterization of graphs G paired with any of these graphs in the role of F . The bipartite case is singled out. It occurs that every nonsingular F is paired with an infinite family of graphs G, and their number is comparatively large even if we exclude the existence of the so-called twin vertices. The latter empirical observation is demonstrated through some examples.