Pivots, determinants, and perfect matchings of graphs

DOI10.1016/J.TCS.2012.02.031zbMATH Open1251.05132arXiv0811.3500OpenAlexW2041707611MaRDI QIDQ714808FDOQ714808

Authors: Robert Brijder, Hendrik Jan Hoogeboom, Tero Harju 

Publication date: 11 October 2012

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

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)