Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching (Q1263603)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching |
scientific article |
Statements
Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching (English)
0 references
1989
0 references
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.
0 references
bipartite graphs
0 references
unique perfect matching
0 references
adjacency matrix
0 references