Nonexistence of almost Moore digraphs of diameter three
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.
- On digraphs of excess one
- On the non-existence of families of \((d,k, \delta)\)-digraphs containing only selfrepeat vertices
- Digraphs with degree two and excess two are diregular
- On diregular digraphs with degree two and excess three
- On networks with order close to the Moore bound
- On total regularity of mixed graphs with order close to the Moore bound
- On the nonexistence of almost Moore digraphs
- On the nonexistence of almost Moore digraphs of degree four and five
- Nonexistence of almost Moore digraphs of degrees 4 and 5 with self-repeats
- A conjecture on the existence of almost Moore digraphs
- On the existence of almost Moore digraphs of diameter three
- Subdigraphs of almost Moore digraphs induced by fixpoints of an automorphism
- Enumeration of almost Moore digraphs of diameter two
- New results regarding the permutation cycle structure of almost Moore digraphs
- On the nonexistence of almost Moore digraphs with self-repeats
This page was built for publication: Nonexistence of almost Moore digraphs of diameter three
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010813)
