On mixed almost Moore graphs of diameter two

MaRDI QIDQ281579zbMATH OpenFDO

Authors Nacho López, Josep M. Miret Biosca

Publication date 11 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p3

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

characteristic polynomialcyclotomic polynomialdegree/diameter problemmixed almost Moore graphpermutation cycle structure

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

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.

Recommendations

• On mixed Moore graphs
• Properties of mixed Moore graphs of directed degree one
• Moore mixed graphs from Cayley graphs
• Construction of extremal mixed graphs of diameter two
• On total regularity of mixed graphs with order close to the Moore bound

Cites work

• A revised Moore bound for mixed graphs
• Almost Moore digraphs are diregular
• Enumeration of almost Moore digraphs of diameter two
• scientific article; zbMATH DE number 3455291 (Why is no real title available?)
• scientific article; zbMATH DE number 3632534 (Why is no real title available?)
• scientific article; zbMATH DE number 637285 (Why is no real title available?)
• scientific article; zbMATH DE number 967875 (Why is no real title available?)
• Maximum degree in graphs of diameter 2
• Non existence of some mixed Moore graphs of diameter 2 using SAT
• On mixed Moore graphs
• On Moore Graphs with Diameters 2 and 3
• On the impossibility of directed Moore graphs
• On the structure of digraphs with order close to the Moore bound

Cited in

(10)

• On networks with order close to the Moore bound
• On total regularity of mixed graphs with order close to the Moore bound
• Construction of extremal mixed graphs of diameter two
• Properties of mixed Moore graphs of directed degree one
• Sequence mixed graphs
• Moore mixed graphs from Cayley graphs
• Almost Moore and the largest mixed graphs of diameters two and three
• On bipartite (1,1,k)-mixed graphs
• On mixed Moore graphs
• Non existence of some mixed Moore graphs of diameter 2 using SAT

This page was built for publication: On mixed almost Moore graphs of diameter two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281579)