Graphs of order two less than the Moore bound

DOI10.1016/J.DISC.2006.06.045MaRDI QIDQ924968zbMATH OpenOpenAlexFDO

Authors Mirka Miller, Rinovia Simanjuntak

Publication date 29 May 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.06.045

zbMATH Keywords

degree/diameter problemMoore boundrepeat

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Review text

The degree/diameter problem asks to determine the largest order \(n_{d,k}\) of a graph of maximum degree at most \(d\) and diameter at most \(k\). It is well known that for \(d\geq 3\) and \(k\geq 3\) the known Moore bound \(M_{d,k}=1+d+d(d-1)+\cdots +d(d-1)^{k-1}\) cannot be attained. In this paper graphs of order \(M_{d,k}- 2\) are studied. The results make use of the notion of a repeat. The main result says that if \(d=4\) and \(k\geq 3\) then there are no such graphs.

Recommendations

• Maximum degree in graphs of diameter 2
• Moore graphs and beyond: a survey of the degree/diameter problem
• Digraphs of degree two which miss the Moore bound by two
• Cayley graphs of diameter two with order greater than 0.684 of the Moore bound for any degree
• A note on large graphs of diameter two and given maximum degree

Cites work

• Diameters of cubic graphs
• Graphs of order two less than the Moore bound
• scientific article; zbMATH DE number 861410 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• Large graphs with given degree and diameter. II
• Large Graphs with Given Degree and Diameter—Part I
• Maximum degree in graphs of diameter 2
• Minimum Diameter of Diregular Digraphs of Degree 2
• New results for the degree/diameter problem
• On Moore Graphs with Diameters 2 and 3
• Regular graphs with excess one

Cited in

(7)

• On networks with order close to the Moore bound
• On graphs of defect at most 2
• Degree/diameter problem for trees and pseudotrees
• Structural properties of graphs of diameter 2 with maximal repeats
• scientific article; zbMATH DE number 4043895 (Why is no real title available?)
• Maximum degree in graphs of diameter 2
• Graphs of order two less than the Moore bound

This page was built for publication: Graphs of order two less than the Moore bound

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