On Mixed Almost Moore Graphs of Diameter Two

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 existence has been considered before for directed graphs and undirected ones, but...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2016-04, Vol.23 (2)
Main Authors: López, Nacho, Miret, Josep M.
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 existence has been considered before for directed graphs and undirected ones, but not for the mixed case, which is a kind of generalization. In this paper we give some necessary conditions for the existence of mixed almost Moore graphs of diameter two derived from the factorization in $\mathbb{Q}[x]$ of their characteristic polynomial. In this context, we deal with the irreducibility of $\Phi_i(x^2+x-(r-1))$, where $\Phi_i(x)$ denotes the i-th cyclotomic polynomial.
ISSN:1077-8926
1077-8926
DOI:10.37236/5647