Applying a combinatorial determinant to count weighted cycle systems in a directed graph

详细信息    查看全文

• 作者：Christopher R.H. Hanusa
• 关键词：Cycle system ; Cycle cover ; Hamburger graph ; Hamburger matrix ; Determinant ; Directed graph
• 刊名：Discrete Mathematics
• 出版年：2009
• 出版时间：6 April 2009
• 年：2009
• 卷：309
• 期：6
• 页码：1746-1748
• 全文大小：282 K

文摘

One method for counting weighted cycle systems in a graph entails taking the determinant of the identity matrix minus the adjacency matrix of the graph. The result of this operation is the sum over cycle systems of −1 to the power of the number of disjoint cycles times the weight of the cycle system. We use this fact to reprove that the determinant of a matrix of much smaller order can be computed to calculate the number of cycle systems in a hamburger graph.