tailieunhanh - Báo cáo toán học: " Nonexistence of almost Moore digraphs of diameter three"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Nonexistence of almost Moore digraphs of diameter three. | Nonexistence of almost Moore digraphs of diameter three J. Conde J. Gimbert Departament de Matemàtica Universitat de Lleida Jaume II 69 25001 Lleida Spain jconde joangim @ J. Gonzalez Departament de Matemàtica Aplicada IV Universitat Politàcnica de Catalunya Victor Balaguer s n 08800 Vilanova i la Geltru Spain josepg@ . Miret R. Moreno Departament de Matemàatica Universitat de Lleida Jaume II 69 25001 Lleida Spain miret ramiro @ Submitted Jul 18 2007 Accepted Jun 21 2008 Published Jun 30 2008 Mathematics Subject Classification 05C20 05C50 11R18 Abstract Almost Moore digraphs appear in the context of the degree diameter problem as a class of extremal directed graphs in the sense that their order is one less than the unattainable Moore bound M d k 1 d dk where d 1 and k 1 denote the maximum out-degree and diameter respectively. So far the problem of their existence has only been solved when d 2 3 or k 2. In this paper we prove that almost Moore digraphs of diameter k 3 do not exist for any degree d. The enumeration of almost Moore digraphs of degree d and diameter k 3 turns out to be equivalent to the search of binary matrices A fulfilling that AJ dJ and I A A2 A3 J P where J denotes the all-one matrix and P is a permutation matrix. We use spectral techniques in order to show that such equation has no Partially supported by the Ministry of Science and Technology Spain under the projects TIC2003-09188 MTM2006-15038-C02-02 and MTM2007-66842-C02-02. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R87 1 0 1 -matrix solutions. More precisely we obtain the factorization in Q x of the characteristic polynomial of A in terms of the cycle structure of P we compute the trace of A and we derive a contradiction on some algebraic multiplicities of the eigenvalues of A. In order to get the factorization of det xI A we determine when the polynomials Fn x n 1 x x2 x3 are irreducible in Q x where ra x denotes the n-th cyclotomic .