Non existence of almost Moore digraphs of diameter three
| dc.contributor.author | Conde Colom, Josep | |
| dc.contributor.author | Gimbert i Quintilla, Joan | |
| dc.contributor.author | Miret, Josep M. (Josep Maria) | |
| dc.contributor.author | Moreno Chiral, Ramiro | |
| dc.contributor.author | Gonzàlez, J. | |
| dc.date.accessioned | 2015-12-18T13:19:17Z | |
| dc.date.available | 2015-12-18T13:19:17Z | |
| dc.date.issued | 2008 | |
| dc.description.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 ful lling 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 (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 n(x) denotes the n-th cyclotomic polynomial, since in such case they become `big pieces' of det(xI - A). By using concepts and techniques from algebraic number theory, we prove that Fn(x) is always irreducible in Q[x], unless n = 1; 10. So, by combining tools from matrix and number theory we have been able to solve a problem of graph theory. | ca_ES |
| dc.description.sponsorship | Partially supported by the Ministry of Science and Technology, Spain, under the projects TIC2003- 09188, MTM2006-15038-C02-02 and MTM2007-66842-C02-02. | |
| dc.identifier.idgrec | 012456 | |
| dc.identifier.issn | 1077-8926 | |
| dc.identifier.uri | http://hdl.handle.net/10459.1/49273 | |
| dc.language.iso | eng | ca_ES |
| dc.publisher | Electronic Journal of Combinatorics | ca_ES |
| dc.relation | info:eu-repo/grantAgreement/MICYT//TIC2003-09188/ES/ | |
| dc.relation | info:eu-repo/grantAgreement/MEC//MTM2006-15038-C02-02/ES/CURVAS MODULARES Y DE SHIMURA Y SUPERFICIES ABELIANAS/ | |
| dc.relation | info:eu-repo/grantAgreement/MEC//MTM2007-66842-C02-02/ES/ALGORITMOS Y PROTOCOLOS CRIPTOGRAFICOS CON CURVAS ELIPTICAS E HIPERELIPTICAS/ | |
| dc.relation.isformatof | Reproducció del document publicat a http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r87 | ca_ES |
| dc.relation.ispartof | Electronic Journal of Combinatorics, 2008, vol. 15, núm. 1 | ca_ES |
| dc.rights | (c) Conde et al., 2008 | ca_ES |
| dc.rights.accessRights | info:eu-repo/semantics/openAccess | ca_ES |
| dc.subject | Almost Moore digraph | ca_ES |
| dc.subject | Characteristic polynomial | ca_ES |
| dc.subject | Cyclotomic polynomial | ca_ES |
| dc.title | Non existence of almost Moore digraphs of diameter three | ca_ES |
| dc.type | article | ca_ES |
| dc.type.version | publishedVersion | ca_ES |