Isotropic matroids. III: Connectivity

MaRDI QIDQ2363112zbMATH OpenFDO

Authors Robert Brijder, L. Traldi

Publication date 13 July 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.03899, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p49

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

circle graphconnectivitydegreeisotropic systemlocal equivalencematroidpendantprimesplittwin

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: The isotropic matroid $M[IAS(G)]$ of a graph $G$ is a binary matroid, which is equivalent to the isotropic system introduced by Bouchet. In this paper we discuss four notions of connectivity related to isotropic matroids and isotropic systems. We show that the isotropic system connectivity defined by Bouchet is equivalent to vertical connectivity of $M[IAS(G)]$, and if $G$ has at least four vertices, then $M[IAS(G)]$ is vertically 5-connected if and only if $G$ is prime (in the sense of Cunningham's split decomposition). We also show that $M[IAS(G)]$ is $3$-connected if and only if $G$ is connected and has neither a pendant vertex nor a pair of twin vertices. Our most interesting theorem is that if $G$ has $ngeq7$ vertices then $M[IAS(G)]$ is not vertically $n$-connected. This abstract-seeming result is equivalent to the more concrete assertion that $G$ is locally equivalent to a graph with a vertex of degree $<fracn-12$.

Review text

Summary: The isotropic matroid \(M[IAS(G)]\) of a graph \(G\) is a binary matroid, which is equivalent to the isotropic system introduced by Bouchet. In this paper we discuss four notions of connectivity related to isotropic matroids and isotropic systems. We show that the isotropic system connectivity defined by Bouchet is equivalent to vertical connectivity of \(M[IAS(G)]\), and if \(G\) has at least four vertices, then \(M[IAS(G)]\) is vertically 5-connected if and only if \(G\) is prime (in the sense of Cunningham's split decomposition). We also show that \(M[IAS(G)]\) is \(3\)-connected if and only if \(G\) is connected and has neither a pendant vertex nor a pair of twin vertices. Our most interesting theorem is that if \(G\) has \(n\geq7\) vertices then \(M[IAS(G)]\) is not vertically \(n\)-connected. This abstract-seeming result is equivalent to the more concrete assertion that \(G\) is locally equivalent to a graph with a vertex of degree \(<\frac{n-1}{2}\). For Part II see [the authors, ibid. 23, No. 4, Research Paper P4.2, 38 p. (2016; Zbl 1351.05044)].

Recommendations

• Isotropic matroids. I: Multimatroids and neighborhoods
• Minimally 3-connected isotropic systems
• scientific article; zbMATH DE number 140137
• scientific article; zbMATH DE number 15493
• scientific article; zbMATH DE number 952951

Cites work

• Algebraic Graph Theory
• Binary matroids and local complementation
• Circle graph obstructions
• Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs
• Decomposition of Directed Graphs
• Fast generation of regular graphs and construction of cages
• Graphic presentations of isotropic systems
• Greedy algorithm and symmetric matroids
• scientific article; zbMATH DE number 15493 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Isotropic matroids. I: Multimatroids and neighborhoods
• Isotropic matroids. II: Circle graphs
• Isotropic systems
• Minimally 3-connected isotropic systems
• Practical graph isomorphism. II.
• Reducing prime graphs and recognizing circle graphs
• The structure of the 3-separations of 3-connected matroids
• The structure of the 3-separations of 3-connected matroids. II.

Cited in

(10)

• Minimally 3-connected isotropic systems
• Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs
• A characterization of circle graphs in terms of multimatroid representations
• Notes on a theorem of Naji
• scientific article; zbMATH DE number 15493 (Why is no real title available?)
• The unbreakable frame matroids
• The lattice of integer flows of a regular matroid
• A binary-matroid analogue of a graph connectivity theorem of Jamison and Mulder
• Isotropic matroids. I: Multimatroids and neighborhoods
• Connectivity in frame matroids

Describes a project that uses

Uses Software

• GENREG
• nauty
• SageMath
• Traces

This page was built for publication: Isotropic matroids. III: Connectivity

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