The average cut-rank of graphs
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huy-Tung Nguyen | - |
dc.contributor.author | Sang-il Oum | - |
dc.date.accessioned | 2020-12-22T02:22:43Z | - |
dc.date.accessioned | 2020-12-22T02:22:43Z | - |
dc.date.available | 2020-12-22T02:22:43Z | - |
dc.date.available | 2020-12-22T02:22:43Z | - |
dc.date.created | 2020-09-09 | - |
dc.date.issued | 2020-12 | - |
dc.identifier.issn | 0195-6698 | - |
dc.identifier.uri | https://pr.ibs.re.kr/handle/8788114/7530 | - |
dc.description.abstract | © 2020 The Author(s). The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i,j)-entry is 1 if the vertex i in X is adjacent to the vertex j in V(G)∖X and 0 otherwise. We introduce the graph parameter called the average cut-rank of a graph, defined as the expected value of the cut-rank of a random set of vertices. We show that this parameter does not increase when taking vertex-minors of graphs and a class of graphs has bounded average cut-rank if and only if it has bounded neighborhood diversity. This allows us to deduce that for each real α, the list of induced-subgraph-minimal graphs having average cut-rank larger than (or at least) α is finite. We further refine this by providing an upper bound on the size of obstruction and a lower bound on the number of obstructions for average cut-rank at most (or smaller than) α for each real α≥0. Finally, we describe explicitly all graphs of average cut-rank at most 3∕2 and determine up to 3∕2 all possible values that can be realized as the average cut-rank of some graph | - |
dc.description.uri | 1 | - |
dc.language | 영어 | - |
dc.publisher | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD | - |
dc.subject | CLIQUE-WIDTH | - |
dc.title | The average cut-rank of graphs | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 000565160300006 | - |
dc.identifier.scopusid | 2-s2.0-85087861305 | - |
dc.identifier.rimsid | 72782 | - |
dc.contributor.affiliatedAuthor | Sang-il Oum | - |
dc.identifier.doi | 10.1016/j.ejc.2020.103183 | - |
dc.identifier.bibliographicCitation | EUROPEAN JOURNAL OF COMBINATORICS, v.90, pp.103183 | - |
dc.citation.title | EUROPEAN JOURNAL OF COMBINATORICS | - |
dc.citation.volume | 90 | - |
dc.citation.startPage | 103183 | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.subject.keywordPlus | CLIQUE-WIDTH | - |