Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching (Q1263603)

Consider the class of bipartite graphs with a unique perfect matching, with the property that when the edges of this perfect matching are contracted, the resulting graph is again bipartite. In Combinatorica 5, 33-39 (1985; Zbl 0578.05049), the reviewer showed that the adjacency matrix of a such a graph G is invertible and diagonally similar to a non- negative matrix. Further, the multigraph \(G^+\) determined by this non- negative matrix contains the original graph as a spanning subgraph. This suggested the problem of determining the graphs G in the above class such that \(G\cong G^+.\) In the paper under review, the authors provide a nice proof that these graphs are precisely the bipartite graphs obtained by taking a bipartite graph and joining a new vertex of degree one to each vertex in it.