Maximal pivots on graphs with an application to gene assembly

DOI10.1016/J.DAM.2010.08.030zbMATH Open1215.05143arXiv0909.3789OpenAlexW2032994838MaRDI QIDQ608283FDOQ608283

Authors: Robert Brijder, Hendrik Jan Hoogeboom 

Publication date: 25 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We consider principal pivot transform (pivot) on graphs. We define a natural variant of this operation, called dual pivot, and show that both the kernel and the set of maximally applicable pivots of a graph are invariant under this operation. The result is motivated by and applicable to the theory of gene assembly in ciliates.

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

Recommendations

• Pivots, determinants, and perfect matchings of graphs
• Graph reductions, binary rank, and pivots in gene assembly
• Pivot and loop complementation on graphs and set systems
• Gene assembly through cyclic graph decomposition
• The structure of elementary strategies for gene assembly in ciliates

zbMATH Keywords

overlap graphprincipal pivot transformalgebraic graph theorygene assembly in ciliates

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Topics in Intersection Graph Theory
• Title not available (Why is that?)
• Principal pivot transforms: Properties and applications
• Title not available (Why is that?)
• Representability of \(\bigtriangleup\)-matroids over \(GF(2)\)
• Title not available (Why is that?)
• Computation in living cells. Gene assembly in ciliates
• Determinantal ideals, Pfaffian ideals, and the principal minor theorem
• A generalization of Tutte's characterization of totally unimodular matrices
• Formal systems for gene assembly in ciliates.
• String and graph reduction systems for gene assembly in ciliates
• Pivots, determinants, and perfect matchings of graphs
• The fibers and range of reduction graphs in ciliates
• Strategies of loop recombination in ciliates

Cited In (7)

• On the linear algebra of local complementation
• Graph reductions, binary rank, and pivots in gene assembly
• Pivots, determinants, and perfect matchings of graphs
• Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
• The group structure of pivot and loop complementation on graphs and set systems
• Sorting by reversals and the theory of 4-regular graphs
• Pivot and loop complementation on graphs and set systems

This page was built for publication: Maximal pivots on graphs with an application to gene assembly

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