2026-04-17T12:44:47Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/229922026-02-07T07:11:56Zcom_2072_1033col_2072_452950

On the nonexistence of almost Moore digraphs Conde Colom, Josep Gimbert Quintilla, Joan González Rovira, Josep Miller, Mirka Miret Biosca, Josep Maria Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV Universitat Politècnica de Catalunya. TN - Grup de Recerca en Teoria de Nombres Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs Graph theory EXISTENCE Grafs, Teoria de Digraphs of maximum out-degree at most d > 1, diameter at most k > 1 and order N(d, k) = d + ... + d(k) are called almost Moore or (d, k)-digraphs. So far, the problem of their existence has been solved only when d = 2, 3 or k = 2, 3, 4. In this paper we derive the nonexistence of (d, k)-digraphs, with k > 4 and d > 3, under the assumption of a conjecture related to the factorization of the polynomials Phi(n)(1 + x + ... + x(k)), where Phi(n)(x) denotes the nth cyclotomic polynomial and 1 < n <= N(d, k). Moreover, we prove that almost Moore digraphs do not exist for the particular cases when k = 5 and d = 4, 5 or 6. (C) 2014 Elsevier Ltd. All rights reserved. Postprint (published version) 2014-07-01 Article Conde, J. [et al.]. On the nonexistence of almost Moore digraphs. "European journal of combinatorics", 01 Juliol 2014, vol. 39, p. 170-177. 0195-6698 https://hdl.handle.net/2117/22992 10.1016/j.ejc.2013.12.003 eng http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Restricted access - publisher's policy Attribution-NonCommercial-NoDerivs 3.0 Spain 8 p. application/pdf