Prime vertex-minors of a prime graph

DOI10.1016/J.EJC.2023.103871arXiv2202.07877OpenAlexW4388749820MaRDI QIDQ6201871FDOQ6201871

Donggyu Kim, Sang-Il Oum

Publication date: 26 March 2024

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

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*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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Circle graph obstructions
• Rank-width and vertex-minors
• Graphic presentations of isotropic systems
• Reducing prime graphs and recognizing circle graphs
• Connectivity in Matroids
• On the structure of 3-connected matroids and graphs
• Isotropic systems
• Rank-Width and Well-Quasi-Ordering
• Circle graph obstructions under pivoting
• Graph-Theoretic Concepts in Computer Science
• The 3-connected graphs with exactly three non-essential edges
• An efficient algorithm to recognize locally equivalent graphs
• On the connectivity function of a matroid
• Matroids and graphs with few non-essential elements
• Minimally 3-connected isotropic systems

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)