Prime vertex-minors of a prime graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912080246865920 |
|---|---|
| author | Kim, Donggyu Oum, Sang-il |
| author_facet | Kim, Donggyu Oum, Sang-il |
| contents | A graph is prime if it does not admit a partition $(A,B)$ of its vertex set such that $\min\{|A|,|B|\} \geq 2$ and the rank of the $A\times B$ 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 $v \ne x$ such that $G \setminus v$ or $G * v \setminus v$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_07877 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Prime vertex-minors of a prime graph Kim, Donggyu Oum, Sang-il Combinatorics 05C50, 05C75, 05C83 G.2.2 A graph is prime if it does not admit a partition $(A,B)$ of its vertex set such that $\min\{|A|,|B|\} \geq 2$ and the rank of the $A\times B$ 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 $v \ne x$ such that $G \setminus v$ or $G * v \setminus v$ 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. |
| title | Prime vertex-minors of a prime graph |
| topic | Combinatorics 05C50, 05C75, 05C83 G.2.2 |
| url | https://arxiv.org/abs/2202.07877 |