期刊
JOURNAL OF COMBINATORIAL THEORY SERIES A
卷 118, 期 2, 页码 350-364出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcta.2010.04.001
关键词
Critical group; De Bruijn graph; Iterated line digraph; Kautz graph; Matrix-tree theorem; Oriented spanning tree; Weighted Laplacian
类别
资金
- NSF
We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs. (C) 2010 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据