This article is cited in 5 papers

Asymptotic Behavior of the Number of Eulerian Orientations of Graphs

M. I. Isaev<sup>ab

a</sup> Centre de Mathématiques Appliquées, École Polytechnique
^b Moscow Institute of Physics and Technology (State University)

Abstract: The class of simple graphs with large algebraic connectivity (the second minimal eigenvalue of the Laplacian matrix) is considered. For graphs of this class, the asymptotic behavior of the number of Eulerian orientations is obtained. New properties of the Laplacian matrix are established, as well as an estimate of the conditioning of matrices with asymptotic diagonal dominance is obtained.

Keywords: simple graph, Eulerian orientation of a graph, algebraic connectivity, Laplacian matrix, matrix with diagonal dominance, spanning tree, conditioning of a matrix.

UDC: 519.175

Received: 03.09.2011
Revised: 21.04.2012

DOI: 10.4213/mzm9249

 English version: Mathematical Notes, 2013, 93:6, 816–829

Bibliographic databases:

• 
• 
• 
• 
• 
•