×

Graph invertibility. (English) Zbl 1298.05265

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.

MSC:

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

Software:

MathOverflow; OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

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.