Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.3

Acyclic Digraphs and Eigenvalues of (0,1)-Matrices

Brendan D. McKay
Department of Computer Science
Australian National University
Canberra, ACT 0200
AUSTRALIA

Fréedérique E. Oggier
Département de Mathématiques
Ecole Polytechnique Fédérale de Lausanne
1015 Lausanne
SWITZERLAND

Gordon F. Royle
Department of Computer Science & Software Engineering
University of Western Australia
35 Stirling Highway
Crawley, WA 6009
AUSTRALIA

N. J. A. Sloane
Internet and Network Systems Research Department
AT&T Shannon Labs
180 Park Avenue
Florham Park, NJ 07932--0971
USA

Ian M. Wanless
Department of Computer Science
Australian National University
Canberra, ACT 0200
AUSTRALIA

Herbert S. Wilf
Mathematics Department
University of Pennsylvania
Philadelphia, PA 19104--6395
USA

Abstract: We show that the number of acyclic directed graphs with n labeled vertices is equal to the number of nxn (0, 1)-matrices whose eigenvalues are positive real numbers.

(Concerned with sequences A003024 A003087 A085506 A086510 and A087488.)

Received May 29 2004; revised version received August 4 2004. Published in Journal of Integer Sequences August 4 2004.