Nonexistence of almost Moore digraphs of diameter three
type: Item
instance of: scholarly article
title: Nonexistence of almost Moore digraphs of diameter three
zbMATH Open document ID: 1163.05318
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129979
full work available at URL: v15i1r87.html
review text: Summary: 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+\dots +d^k\), 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+A^2+A^3=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 \({\mathbb 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 \(F_n(x)=\Phi_n(1+x+x^2+x^3)\) are irreducible in \({\mathbb Q}[x]\), where \(\Phi_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 \(F_n(x)\) is always irreducible in \({\mathbb 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 11R18
zbMATH DE Number: 5540992
zbMATH Keywords: almost Moore digraph
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: cyclotomic polynomial
zbMATH Keywords: per-
author: Josep Conde
author: Joan Gimbert
author: Josep González
author: Josep M. Miret Biosca
author: Ramiro Moreno
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540992