Graph invertibility

DOI10.1007/S00373-013-1319-7MaRDI QIDQ742608zbMATH OpenOpenAlexFDO

Authors Cam McLeman, Erin McNicholas

Publication date 19 September 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3588

zbMATH Keywords

digraphinverse graphtransitive closureunicyclic graphunique perfect matching

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Extending the work of Godsil and others, we investigate the notion of the inverse of a graph (specifically, of bipartite graphs with a unique perfect matching). We provide a concise necessary and sufficient condition for the invertibility of such graphs and generalize the notion of invertibility to multigraphs. We examine the question of whether there exists a "litmus subgraph" whose bipartiteness determines invertibility. As an application of our invertibility criteria, we quickly describe all invertible unicyclic graphs. Finally, we describe a general combinatorial procedure for iteratively constructing invertible graphs, giving rise to large new families of such graphs.

Recommendations

• Inverses of bicyclic graphs
• On a construction of integrally invertible graphs and their spectral properties
• Inverses of bipartite graphs
• Inverses of weighted graphs
• On the inverse of a class of weighted graphs

Cites work

• Directed intervals and the dual of a graph
• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• Inverses of trees
• Motzkin numbers
• On unimodular graphs
• Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching
• Which Nonnegative Matrices Are Self-Inverse?

Cited in

(21)

• Reverse binary graphs
• Some spectral invariants of the neighborhood corona of graphs
• Partially ordering the class of invertible trees
• Distance spectrum, 1-factor and vertex-disjoint cycles
• Invertible graphs of finite groups
• On a construction of integrally invertible graphs and their spectral properties
• Graph invertibility and median eigenvalues
• A note on inverses of labeled graphs
• scientific article; zbMATH DE number 4114683 (Why is no real title available?)
• Inverses of non-bipartite unicyclic graphs with a unique perfect matching
• Strongly self-inverse weighted graphs
• Inverting non-invertible labeled trees
• Generalized inverses in graph theory
• Group inverses of weighted trees
• Group inverses of a class of corona networks
• On the Moore-Penrose pseudo-inversion of block symmetric matrices and its application in the graph theory
• Inverse of \(\alpha\)-Hermitian adjacency matrix of a unicyclic bipartite graph
• Qualitative, statistical, and extreme properties of spectral indices of signable pseudo-invertible graphs
• On sign-invertible graphs
• On generalized inverses of matrices associated with certain graph classes
• Inverting graphs of rectangular matrices

Describes a project that uses

Uses Software

• MathOverflow
• OEIS

This page was built for publication: Graph invertibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742608)