Prime vertex-minors of a prime graph

DOI10.1016/J.EJC.2023.103871MaRDI QIDQ6201871zbMATH OpenOpenAlexFDO

Authors Donggyu Kim, Sang-Il Oum

Publication date 26 March 2024

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

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

zbMATH Keywords

cycle graphpivot-minors

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40)

Abstract: A graph is prime if it does not admit a partition $(A,B)$ of its vertex set such that $min|A|,|B|geq2$ and the rank of the $AimesB$ submatrix of its adjacency matrix is at most $1$. A vertex $v$ of a graph is non-essential if at least two of the three kinds of vertex-minor reductions at $v$ result in prime graphs. In 1994, Allys proved that every prime graph with at least four vertices has a non-essential vertex unless it is locally equivalent to a cycle graph. We prove that every prime graph with at least four vertices has at least two non-essential vertices unless it is locally equivalent to a cycle graph. As a corollary, we show that for a prime graph $G$ with at least six vertices and a vertex $x$, there is a vertex $vex$ such that $Gsetminusv$ or $G\ast vsetminusv$ is prime, unless $x$ is adjacent to all other vertices and $G$ is isomorphic to a particular graph on odd number of vertices. Furthermore, we show that a prime graph with at least four vertices has at least three non-essential vertices, unless it is locally equivalent to a graph consisting of at least two internally-disjoint paths between two fixed distinct vertices having no common neighbors. We also prove analogous results for pivot-minors.

Recommendations

• Unavoidable vertex-minors in large prime graphs
• On minimal prime extensions of a four-vertex graph in a prime graph
• scientific article; zbMATH DE number 5720921
• Recognition of prime graphs from a prime subgraph
• Rank connectivity and pivot-minors of graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 4202305 (Why is no real title available?)
• scientific article; zbMATH DE number 4002273 (Why is no real title available?)
• scientific article; zbMATH DE number 15493 (Why is no real title available?)
• scientific article; zbMATH DE number 26598 (Why is no real title available?)
• scientific article; zbMATH DE number 4183450 (Why is no real title available?)
• An efficient algorithm to recognize locally equivalent graphs
• Circle graph obstructions
• Circle graph obstructions under pivoting
• Connectivity in Matroids
• Graph-Theoretic Concepts in Computer Science
• Graphic presentations of isotropic systems
• Isotropic systems
• Matroids and graphs with few non-essential elements
• Minimally 3-connected isotropic systems
• On the connectivity function of a matroid
• On the structure of 3-connected matroids and graphs
• Rank-Width and Well-Quasi-Ordering
• Rank-width and vertex-minors
• Reducing prime graphs and recognizing circle graphs
• The 3-connected graphs with exactly three non-essential edges

Cited in

(1)

• Vertex-minors of graphs: a survey

This page was built for publication: Prime vertex-minors of a prime graph

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