Non--Singular Bipartite Graphs with a Singular Deck

Alexander Farrugia
University of Malta



Content: A NSSD is an undirected, non--singular graph on $n$ vertices with weighted edges and no loops whose $n$ vertex--deleted subgraphs are all singular. A graph with adjacency matrix {\bf G} is a NSSD if and only if the graph with adjacency matrix ${\bf G}^{-1}$ is a NSSD. We show that this also holds for the subclass of bipartite NSSDs, that is, the inverse of the adjacency matrix of a bipartite NSSD is the adjacency matrix of another bipartite NSSD. Furthermore, we show that bipartite NSSDs must have an even number of vertices. We then focus on NSSD trees, which are a subclass of bipartite NSSDs, and provide a characterisation of this subclass by a constructive argument. Moreover, we show a Fiedler--type result that any NSSD tree remains an NSSD tree if its nonzero edge weights are changed to other arbitrary nonzero real numbers.

Back to all abstracts