Maximal pivots on graphs with an application to gene assembly

DOI10.1016/J.DAM.2010.08.030MaRDI QIDQ608283zbMATH OpenOpenAlexFDO

Authors Robert Brijder, Hendrik Jan Hoogeboom

Publication date 25 November 2010

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

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

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)

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.

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

Cites work

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

Cited in

(7)

• Pivot and loop complementation on graphs and set systems
• 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

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)