The number of n-cycles in a graph

摘要

Recently, Chang and Fu [Y.C. Chang, H.L. Fu, The number of 6-cycles in a graph, Bull. Inst. Combin. Appl. 39 (2003) 27–30] derived an exact expression, based on powers of the adjacency matrix, for the number of 6-cycles in a graph. Here, I demonstrate a method for obtaining the number of n-cycles in a graph from the immanants of the adjacency matrix. The method is applicable to cycles of all sizes and to sets of disjoint cycles of any sizes, and the cycles in the set need not be the same size.