{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T07:14:03Z","timestamp":1780989243914,"version":"3.54.1"},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2010,7,21]],"date-time":"2010-07-21T00:00:00Z","timestamp":1279670400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>The line graph <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000192_char1\"\/><\/jats:private-char><jats:italic>G<\/jats:italic> of a directed graph <jats:italic>G<\/jats:italic> has a vertex for every edge of <jats:italic>G<\/jats:italic> and an edge for every path of length 2 in <jats:italic>G<\/jats:italic>. In 1967, Knuth used the Matrix Tree Theorem to prove a formula for the number of spanning trees of <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000192_char1\"\/><\/jats:private-char><jats:italic>G<\/jats:italic>, and he asked for a bijective proof [6]. In this paper, we give a bijective proof of Knuth's formula. As a result of this proof, we find a bijection between binary de Bruijn sequences of degree <jats:italic>n<\/jats:italic> and binary sequences of length 2<jats:sup><jats:italic>n<\/jats:italic>\u22121<\/jats:sup>. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine [7].<\/jats:p>","DOI":"10.1017\/s0963548310000192","type":"journal-article","created":{"date-parts":[[2010,7,21]],"date-time":"2010-07-21T08:58:01Z","timestamp":1279702681000},"page":"11-25","source":"Crossref","is-referenced-by-count":8,"title":["A Bijective Proof of a Theorem of Knuth"],"prefix":"10.1017","volume":"20","author":[{"given":"HODA","family":"BIDKHORI","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"SHAUNAK","family":"KISHORE","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2010,7,21]]},"reference":[{"key":"S0963548310000192_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10139"},{"key":"S0963548310000192_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00252-5"},{"key":"S0963548310000192_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(67)80101-7"},{"key":"S0963548310000192_ref1","unstructured":"[1] Berget A. , Manion A. , Maxwell M. , Potechin A. and Reiner V. The critical group of a line graph. arXiv:0904.1246."},{"key":"S0963548310000192_ref2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018611014097"},{"key":"S0963548310000192_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-8786-0_17"},{"key":"S0963548310000192_ref7","unstructured":"[7] Levine L. (2010) Sandpile groups and spanning trees of directed line graphs. To appear in Journal of Combinatorial Theory, Series A. arXiv:0906.2809."},{"key":"S0963548310000192_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T15:57:04Z","timestamp":1556380624000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000192\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,21]]},"references-count":8,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["S0963548310000192"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000192","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,21]]}}}