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
