Báo cáo toán học: "A q-analogue of Graham, Hoffman and Hosoya’s Theorem"

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 q-analogue of Graham, Hoffman and Hosoya’s Theorem. | A q-analogue of Graham Hoffman and Hosoya s Theorem Sivaramakrishnan Sivasubramanian Department of Mathematics Indian Institute of Technology Bombay krishnan@ Submitted Apr 23 2009 Accepted Apr 7 2010 Published Apr 19 2010 Mathematics Subject Classification 05A30 05C12 Abstract Graham Hoffman and Hosoya gave a very nice formula about the determinant of the distance matrix Dg of a graph G in terms of the distance matrix of its blocks. We generalize this result to a q-analogue of Dg. Our generalization yields results about the equality of the determinant of the mod-2 and in general mod-k distance matrix . each entry of the distance matrix is taken modulo 2 or k of some graphs. The mod-2 case can be interpreted as a determinant equality result for the adjacency matrix of some graphs. 1 Introduction Graham and Pollak see 3 considered the distance matrix DT du v of a tree T V E . For u v G V its distance du v is the length of a shortest in this case unique path between u and v in T and since any tree is connected all entries du v are finite. Let DT be the distance matrix of T with V n. They showed a surprising result that det DT 1 n-1 n 1 2n 2. Thus the determinant of DT only depends on n the number of vertices of T and is independent of T s structure. Graham Hoffman and Hosoya 2 proved a very attractive theorem about the determinant of the distance matrix DG of a strongly connected digraph G as a function of the distance matrix of its 2-connected blocks also called blocks . Denote the sum of the cofactors of a matrix A as cofsum A . Graham Hoffman and Hosoya see 2 showed the following. Theorem 1 If G is a strongly connected digraph with 2-connected blocks G1 G2 . Gr then cofsum DG nr 1 cofsum DG. anddet DG Ỵfi 1 det DG. n i cofsum DGj . Since all the n 1 blocks of any tree T on n vertices are K2 s we can recover Graham and Pollak s K ult hmm Theorem 1. Yan and Yeh 5 showed a similar tree structure independent THE ELECTRONIC JOURNAL OF COMBINATORICS 17