DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, Donggyu | ko |
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2023-12-26T01:00:13Z | - |
dc.date.available | 2023-12-26T01:00:13Z | - |
dc.date.created | 2023-12-24 | - |
dc.date.issued | 2024-05 | - |
dc.identifier.citation | EUROPEAN JOURNAL OF COMBINATORICS, v.118 | - |
dc.identifier.issn | 0195-6698 | - |
dc.identifier.uri | http://hdl.handle.net/10203/316856 | - |
dc.description.abstract | A graph is prime if it does not admit a partition (A, B) of its vertex set such that min{vertical bar A vertical bar, vertical bar B vertical bar} >= 2 and the rank of the AxB 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 not equal x such that G \ v or G * v \ 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. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD | - |
dc.title | Prime vertex-minors of a prime graph | - |
dc.type | Article | - |
dc.identifier.wosid | 001120714700001 | - |
dc.identifier.scopusid | 2-s2.0-85177242163 | - |
dc.type.rims | ART | - |
dc.citation.volume | 118 | - |
dc.citation.publicationname | EUROPEAN JOURNAL OF COMBINATORICS | - |
dc.identifier.doi | 10.1016/j.ejc.2023.103871 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | RANK-WIDTH | - |
dc.subject.keywordPlus | CONNECTIVITY | - |
dc.subject.keywordPlus | MATROIDS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.