tailieunhanh - Báo cáo toán học: "A Note on the Critical Group of a Line Graph"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A Note on the Critical Group of a Line Graph. | A Note on the Critical Group of a Line Graph David Perkinson Department of Mathematics Reed College davidp@ Nick Salter Department of Mathematics University of Chicago nks@ Tianyuan Xu Department of Mathematics University of Oregon eddyapp@ Submitted Aug 19 2010 Accepted May 25 2011 Published Jun 6 2011 Mathematics Subject Classification 05C20 05C25 05C76 Abstract This note answers a question posed by Levine in 3 . The main result is Theorem 1 which shows that under certain circumstances a critical group of a directed graph is the quotient of a critical group of its directed line graph. 1 Introduction Let G be a finite multidigraph with vertices V and edges E. Loops are allowed in G and we make no connectivity assumptions. Each edge e G E has a tail e- and a target e . Let ZV and ZE be the free abelian groups on V and E respectively. The Laplacian1 of G is the Z-linear mapping Ac ZV ZV determined by AG v X vu eE u - v for v G V. Given w G V define ộ Ộg w ZV ZV i Ag v v 1 w if v w if v w . The critical group for G with respect to w is the cokernel of ộ K G w cokộ. 1The mapping A ZV ZV defined by A f v X v u EE f v f u for v G V is often called the Laplacian of G. It is the negative Z-dual . the transpose of AG. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P124 1 The line graph LG for G is the multidigraph whose vertices are the edges of G and whose edges are e f with e f -. As with G we have the Laplacian ALG and the critical group K LG e cokộcc et for each e G E. If every vertex of G has a directed path to w then K G w is called the sandpile group for G with sink w . A directed spanning tree of G rooted at w is a directed subgraph containing all of the vertices of G having no directed cycles and for which w has out-degree 0 and every other vertex has out-degree 1. Let k G w denote the number of directed spanning trees rooted at w . It is a well-known consequence of the matrix-tree theorem that the number of elements of the .