The Number of Digraphs with Cycles of Length <i>k</i>

• 作者: Chuanlong Wang Mudaster Sidik Xuerong Yong
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: ACYCLIC DIGRAPH EIGENVALUE Power DIGRAPH (0 1)-Matrix
• 年，卷（期）: 2014,（1）
• 页码范围: 6-8
• 页数: 3页
• 分类号: O1

摘要

In this note, we show that the number of digraphs with n vertices and with cycles of length k, 0 ≤ k ≤ n, is equal to the number of n × n (0,1)-matrices whose eigenvalues are the collection of copies of the entire kth unit roots plus, possibly, 0’s. In particular, 1) when k = 0, since the digraphs reduce to be acyclic, our result reduces to the main theorem obtained recently in [1] stating that, for each n = 1, 2, 3, …, the number of acyclic digraphs is equal to the number of n × n (0,1)-matrices whose eigenvalues are positive real numbers;and 2) when k = n, the digraphs are the Hamiltonian directed cycles and it, therefore, generates another well-known (and trivial) result: the eigenvalues of a Hamiltonian directed cycle with n vertices are the nth unit roots [2].