Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14294
Title: | Pivots, determinants, and perfect matchings of graphs | Authors: | BRIJDER, Robert Harju, Tero Hoogeboom, Hendrik Jan |
Issue Date: | 2012 | Publisher: | ELSEVIER SCIENCE BV | Source: | THEORETICAL COMPUTER SCIENCE, 454, p. 64-71 | Abstract: | We consider sequences of local and edge complementations on graphs with loops (we allow local complementation only on looped vertices). We recall that these operations together form the matrix operation of principal pivot transform (or pivot) restricted to graphs. This fact is not well known, and as a consequence various special cases of the properties of pivot have been rediscovered multiple times. In this paper we give a gentle overview of various properties of pivot for local and edge complementations on graphs. Moreover, we relate the pivot operation to perfect matchings to obtain a purely graph-theoretical characterization of the effect of sequences of pivot operations. Finally, we show that two of the three operations that make up a formal graph model of the biological process of gene assembly in ciliates together form the matrix operation of Schur complement restricted to graphs. (C) 2012 Elsevier B.V. All rights reserved. | Notes: | [Brijder, Robert] Hasselt Univ, Dept WET INF, B-3590 Diepenbeek, Belgium. [Brijder, Robert] Transnatl Univ Limburg, Limburg, Belgium. [Harju, Tero] Univ Turku, Dept Math, FI-20014 Turku, Finland. [Hoogeboom, Hendrik Jan] Leiden Univ, Leiden Inst Adv Comp Sci, NL-2300 RA Leiden, Netherlands. robert.brijder@uhasselt.be | Keywords: | Principal pivot transform; Perfect matchings; Gene assembly in ciliates; Local complementation; Circle graph;Computer Science, Theory & Methods; principal pivot transform; perfect matchings; gene assembly in ciliates; local complementation; circle graph | Document URI: | http://hdl.handle.net/1942/14294 | ISSN: | 0304-3975 | e-ISSN: | 1879-2294 | DOI: | 10.1016/j.tcs.2012.02.031 | ISI #: | 000308452100008 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2013 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Pivots, determinants, and perfect matchings of graphs.pdf | Published version | 250.69 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
1
checked on Sep 28, 2024
Page view(s)
64
checked on Sep 6, 2022
Download(s)
96
checked on Sep 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.