McLeman, Cam; McNicholas, Erin Graph invertibility. (English) Zbl 1298.05265 Graphs Comb. 30, No. 4, 977-1002 (2014). Summary: 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. Cited in 11 Documents MathOverflow Questions: Partitions into 0,1, and 2 with a partial sum condition. MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles Keywords:inverse graph; unique perfect matching; digraph; transitive closure; unicyclic graph Software:MathOverflow; OEIS PDFBibTeX XMLCite \textit{C. McLeman} and \textit{E. McNicholas}, Graphs Comb. 30, No. 4, 977--1002 (2014; Zbl 1298.05265) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle. References: [1] Harary, F., Minc H.: Which nonnegative matrices are self-inverse? Math. Mag. (Mathematical Association of America) 49(2), 91-92 (1976) · Zbl 0321.15008 [2] Godsil C.D.: Inverses of trees. Combinatorica 5(1), 33-39 (1985) · Zbl 0578.05049 [3] Tifenbach R., Kirkland S.: Directed intervals and the dual of a graph. Linear Algebra Appl. 431, 792-807 (2009) · Zbl 1226.05171 [4] Akbari S., Kirkland S.: On unimodular graphs. Linear Algebra Appl. 421, 3-15 (2001) · Zbl 1108.05060 [5] Aigner, M.: Combinatorial Theory. Springer, New York (1979) · Zbl 0415.05001 [6] Speyer, D.: Partitions into 0,1, and 2 with a partial sum condition. http://mathoverflow.net/questions/64802 (version: 12th May 2011) [7] Simion R., Cao D.: Solution to a problem of C.D. Godsil regarding bipartite graphs with unique perfect matching. Combinatorica 9(1), 85-89 (1989) · Zbl 0688.05056 [8] The on-line Encyclopedia of integer sequences, published electronically at http://oeis.org/wiki/Welcome#Referencing_the_OEIS, (2011). Sequence A001006 · Zbl 1108.05060 [9] Donaghey R., Shapiro L.W.: Motzkin numbers. J. Comb. Theory Ser. A 23, 201-301 (1977) · Zbl 0417.05007 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.