Non existence of almost Moore digraphs of diameter three
Gimbert i Quintilla, Joan
Moreno Chiral, Ramiro
MetadataShow full item record
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.
Is part ofElectronic Journal of Combinatorics, 2008, vol. 15, núm. 1
European research projects
Showing items related by title, author, creator and subject.
López Lorenzo, Ignacio; Miret, Josep M. (Josep Maria) (Electronic Journal of Combinatorics, 2016-04-01)Mixed almost Moore graphs appear in the context of the Degree/Diameter problem as a class of extremal mixed graphs, in the sense that their order is one less than the Moore bound for mixed graphs. The problem of their ...
Miret, Josep M. (Josep Maria); Moreno Chiral, Ramiro; Pujolàs Boix, Jordi; Valls Marsal, Magda (Institut d'Estudis Catalans. Secció de Ciències i Tecnologia, 2007)En els darrers anys, la criptografia amb corbes el.líptiques ha adquirit una importància creixent, fins a arribar a formar part en la actualitat de diferents estàndards industrials. Tot i que s'han dissenyat variants amb ...
Miret, Josep M. (Josep Maria); Moreno Chiral, Ramiro; Rio, Anna (Universitat Autònoma de Barcelona. Departament de Matemàtiques, 2007)Given an elliptic curve E and a finite subgroup G, V ́lu’s formulae concern to a separable isogeny IG : E → E ′ with kernel G. In particular, for a point P ∈ E these formulae express the first elementary symmetric polynomial ...