On the class of graphs with strong mixing properties
From MaRDI portal
Publication:6231992
arXiv1203.6880MaRDI QIDQ6231992FDOQ6231992
Authors: M. I. Isaev, K. V. Isaeva 
Publication date: 30 March 2012
Abstract: We study three mixing properties of a graph: large algebraic connectivity, large Cheeger constant (isoperimetric number) and large spectral gap from 1 for the second largest eigenvalue of the transition probability matrix of the random walk on the graph. We prove equivalence of this properties (in some sense). We give estimates for the probability for a random graph to satisfy these properties. In addition, we present asymptotic formulas for the numbers of Eulerian orientations and Eulerian circuits in an undirected simple graph.
This page was built for publication: On the class of graphs with strong mixing properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6231992)
