Rank connectivity and pivot-minors of graphs

DOI10.1016/J.EJC.2022.103634zbMATH Open1504.05177arXiv2011.03205OpenAlexW3099641639MaRDI QIDQ2107500FDOQ2107500

Authors: Sang-Il Oum 

Publication date: 1 December 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The cut-rank of a set $X$ in a graph $G$ is the rank of the $Ximes(V(G)-X)$ submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets $(X,Y)$ such that the cut-rank of $X$ is less than $2$ and both $X$ and $Y$ have at least two vertices. A graph is prime (with respect to the split decomposition) if it is connected and has no splits. A graph $G$ is $k^{+ell}$-rank-connected if for every set $X$ of vertices with the cut-rank less than $k$, $lvertXvert$ or $lvertV(G)-Xvert$ is less than $k+ell$. We prove that every prime $3^{+2}$-rank-connected graph $G$ with at least $10$ vertices has a prime $3^{+3}$-rank-connected pivot-minor $H$ such that $lvertV(H)vert=lvertV(G)vert-1$. As a corollary, we show that every excluded pivot-minor for the class of graphs of rank-width at most $k$ has at most $(3.5cdot{6}^k-1)/5$ vertices for $kge2$. We also show that the excluded pivot-minors for the class of graphs of rank-width at most $2$ have at most $16$ vertices.

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

Recommendations

• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Tree pivot-minors and linear rank-width
• Computing small pivot-minors
• The average cut-rank of graphs
• Rank-width and vertex-minors

zbMATH Keywords

\(k^{+\ell}\)-rank-connected graphcut-rank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Connectivity (05C40)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Title not available (Why is that?)
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Matrices and matroids for systems analysis
• Decomposition of Directed Graphs
• Reducing prime graphs and recognizing circle graphs
• A simple theorem on 3-connectivity
• A Splitter Theorem for Internally 4‐Connected Binary Matroids
• Title not available (Why is that?)
• Generating weakly 4-connected matroids
• A chain theorem for 4-connected matroids
• A decomposition theory for matroids. I: General results
• Prime Testing for the Split Decomposition of a Graph
• Rank-width: algorithmic and structural results
• Minimally 3-connected isotropic systems

Cited In (8)

• On the minimum hybrid rank of a graph relative to a partition of its edges and its application to electrical network analysis
• Intertwining Connectivities for Vertex-Minors and Pivot-Minors
• Some connectivity properties for excluded minors of the graph invariant \(\nu(G)\)
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Vertex-minors of graphs: a survey
• A chain theorem for sequentially 3-rank-connected graphs with respect to vertex-minors
• The Minset-Poset Approach to Representations of Graph Connectivity
• Connectivity, graph minors, and subgraph multiplicity

This page was built for publication: Rank connectivity and pivot-minors of graphs

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