Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Inverses of bipartite graphs - MaRDI portal

Inverses of bipartite graphs (Q1715079)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Inverses of bipartite graphs
scientific article

    Statements

    Inverses of bipartite graphs (English)
    0 references
    0 references
    0 references
    1 February 2019
    0 references
    Let $G$ be a bipartite graph with adjacency matrix $A$. If $G$ has a unique perfect matching, then $A$ has an inverse $A^{-1}$ which is a symmetric integral matrix, and hence the adjacency matrix of a multigraph. The inverses of bipartite graphs with unique perfect matchings have a strong connection to Möbius functions of posets. In this note, the authors characterize all bipartite graphs with a unique perfect matching whose adjacency matrices have inverses diagonally similar to non-negative matrices, which settles an open problem of \textit{C. D. Godsil} [Combinatorica 5, 33--39 (1985; Zbl 0578.05049)]. The paper contains no applications despite there are many applications for bipartite graphs.
    0 references
    0 references
    bipartite graph
    0 references
    inverses of bipartite graphs
    0 references
    Möbius functions of posets
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references