Counting the spanning trees of a directed line graph

Details Counting the spanning trees of a directed line graph Counting the spanning trees of a directed line graph

2009-10-19

arxiv.org/abs/0910.3442v1

Mathematics

Combinatorics

14 pages, 3 figures

Scientific paper

The line graph LG of a directed graph G has a vertex for every edge of G and an edge for every path of length 2 in G. In 1967, Knuth used the Matrix-Tree Theorem to prove a formula for the number of spanning trees of LG, and he asked for a bijective proof. In this paper, we give a bijective proof of a generating function identity due to Levine which generalizes Knuth's formula. As a result of this proof we find a bijection between binary de Bruijn sequences of degree n and binary sequences of length 2^{n-1}. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine.

Affiliated with

Also associated with

No associations

Rating

Counting the spanning trees of a directed line graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting the spanning trees of a directed line graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting the spanning trees of a directed line graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-715972