Pivots, determinants, and perfect matchings of graphs

DOI10.1016/J.TCS.2012.02.031MaRDI QIDQ714808zbMATHOpenAlexFDO

Authors Robert Brijder, Hendrik Jan Hoogeboom, Tero Harju

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

perfect matchingsprincipal pivot transformlocal complementationcircle graphgene assembly in ciliates

Mathematics Subject Classification ID

Applications of graph theory (05C90) Genetics and epigenetics (92D10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We give a characterization of the effect of sequences of pivot operations on a graph by relating it to determinants of adjacency matrices. This allows us to deduce that two sequences of pivot operations are equivalent iff they contain the same set S of vertices (modulo two). Moreover, given a set of vertices S, we characterize whether or not such a sequence using precisely the vertices of S exists. We also relate pivots to perfect matchings to obtain a graph-theoretical characterization. Finally, we consider graphs with self-loops to carry over the results to sequences containing both pivots and local complementation operations.

Recommendations

• Maximal pivots on graphs with an application to gene assembly
• Pivot and loop complementation on graphs and set systems
• The group structure of pivot and loop complementation on graphs and set systems
• Graph reductions, binary rank, and pivots in gene assembly
• Graph theoretic approach to parallel gene assembly

Cites work

• scientific article; zbMATH DE number 3156382 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 3432469 (Why is no real title available?)
• scientific article; zbMATH DE number 3257167 (Why is no real title available?)
• A generalization of Tutte's characterization of totally unimodular matrices
• Characterizing the micronuclear gene patterns in ciliates
• Computation in living cells. Gene assembly in ciliates
• Edge local complementation and equivalence of binary linear codes
• Formal systems for gene assembly in ciliates.
• Graph reductions, binary rank, and pivots in gene assembly
• Local unitary versus local Clifford equivalence of stabilizer states
• Parallelism in gene assembly
• Pivots, determinants, and perfect matchings of graphs
• Principal pivot transforms: Properties and applications
• Rank-width and vertex-minors
• String and graph reduction systems for gene assembly in ciliates
• The group structure of pivot and loop complementation on graphs and set systems
• The interlace polynomial of a graph
• The parity of the number of 1-factors of a graph
• Transforming cabbage into turnip

Cited in

(9)

• The group structure of pivot and loop complementation on graphs and set systems
• Pivot and loop complementation on graphs and set systems
• Graph reductions, binary rank, and pivots in gene assembly
• Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs
• Pivots, determinants, and perfect matchings of graphs
• Binary symmetric matrix inversion through local complementation
• scientific article; zbMATH DE number 929718 (Why is no real title available?)
• Nullity invariance for pivot and the interlace polynomial
• Maximal pivots on graphs with an application to gene assembly

This page was built for publication: Pivots, determinants, and perfect matchings of graphs

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