The cut-rank of a set X of vertices in a graph G is defined as the rank of the X 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 alpha, the list of induced-subgraphminimal graphs having average cut-rank larger than (or at least) alpha 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) alpha for each real alpha >= 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.

- Issue Date
- 2020-12

- Language
- English

- Article Type
- Article

- Citation
EUROPEAN JOURNAL OF COMBINATORICS, v.90

- ISSN
- 0195-6698

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item
- 000565160300006.pdf
*(573.57 kB)*Download

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.