The average cut-rank of graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 37
  • Download : 7
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.
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Issue Date
2020-12
Language
English
Article Type
Article
Citation

EUROPEAN JOURNAL OF COMBINATORICS, v.90

ISSN
0195-6698
DOI
10.1016/j.ejc.2020.103183
URI
http://hdl.handle.net/10203/276403
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
000565160300006.pdf(573.57 kB)Download

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0