|
|||||
|
|
Expected values of parameters associated with the minimum rank of a graph |
|
| Authors: | H Tracy Hall Ryan Martin |
| Institution: | a Department of Mathematics, Brigham Young University, Provo UT 84602, USA b Department of Mathematics, Iowa State University, Ames, IA 50011, USA c American Institute of Mathematics, 360 Portage Ave, Palo Alto, CA 94306, USA d Department of Mathematics, University of Wyoming, Laramie, WY 82071, USA |
| Abstract: | We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/maximum nullity and related Colin de Verdière-type parameters. Let G(v,p) denote the usual Erd?s-Rényi random graph on v vertices with edge probability p. We obtain bounds for the expected value of the random variables mr(G(v,p)), M(G(v,p)), ν(G(v,p)) and ξ(G(v,p)), which yield bounds on the average values of these parameters over all labeled graphs of order v. |
| Keywords: | 05C50 05C80 15A03 |
| 本文献已被 ScienceDirect 等数据库收录！ | |