DC Field | Value | Language |
---|---|---|
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2023-01-09T02:00:09Z | - |
dc.date.available | 2023-01-09T02:00:09Z | - |
dc.date.created | 2023-01-09 | - |
dc.date.issued | 2023-02 | - |
dc.identifier.citation | EUROPEAN JOURNAL OF COMBINATORICS, v.108 | - |
dc.identifier.issn | 0195-6698 | - |
dc.identifier.uri | http://hdl.handle.net/10203/304135 | - |
dc.description.abstract | The cut-rank of a set X in a graph G is the rank of the X x (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+l-rank-connected if for every set X of vertices with the cut-rank less than k, |X| or |V(G) - X| is less than k + l. 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 |V(H)| = |V(G)| - 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.5 middot 6k - 1)/5 vertices for k >= 2. We also show that the excluded pivot-minors for the class of graphs of rank-width at most 2 have at most 16 vertices.(c) 2022 Elsevier Ltd. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD | - |
dc.title | Rank connectivity and pivot-minors of graphs | - |
dc.type | Article | - |
dc.identifier.wosid | 000896749600001 | - |
dc.identifier.scopusid | 2-s2.0-85141968083 | - |
dc.type.rims | ART | - |
dc.citation.volume | 108 | - |
dc.citation.publicationname | EUROPEAN JOURNAL OF COMBINATORICS | - |
dc.identifier.doi | 10.1016/j.ejc.2022.103634 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | THEOREM | - |
dc.subject.keywordPlus | DECOMPOSITION | - |
dc.subject.keywordPlus | WIDTH | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.