Non-existence of bipartite graphs of diameter at least 4 and defect 2

DOI10.1007/S10801-010-0266-0MaRDI QIDQ644679zbMATH OpenOpenAlexFDO

Authors Guillermo Pineda-Villavicencio

Publication date 7 November 2011

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10801-010-0266-0

zbMATH Keywords

degree/diameter problemMoore bipartite boundMoore bipartite graphs, Dickson polynomials of the second kindMoore graphs

Mathematics Subject Classification ID

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

Review text

This paper proves a conjecture by settling the non-existence of bipartite \((\Delta,D,-2)\) graphs for all \(\Delta \geq 3\) and all \(D \geq 6\), using the reasoning in the proofs of the non-existence of Moore graphs for \(\Delta\geq 3\) and \(D\geq 3\) and the non-existence of regular graphs of degree \(\Delta\geq 3\), even girth \(g\geq 2\) and order \(M^b_{\Delta,g/2}+2\) and the non-existence of regular graphs of \(\Delta\geq 3\) odd girth \(g\geq 5\) and order \(M_{\Delta,(g-1)/2}+1\).

Recommendations

• On bipartite graphs of diameter 3 and defect 2
• On bipartite graphs of defect at most 4
• On bipartite graphs of defect 2
• Nonexistence of graphs with cyclic defect
• On the nonexistence of graphs of diameter 2 and defect 2

Cites work

• Feasibility conditions for the existence of walk-regular graphs
• Graphs with even girth and small excess
• scientific article; zbMATH DE number 1292563 (Why is no real title available?)
• scientific article; zbMATH DE number 732318 (Why is no real title available?)
• scientific article; zbMATH DE number 2010366 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• Minimal Regular Graphs of Girths Eight and Twelve
• Moore graphs and beyond: a survey of the degree/diameter problem
• Nonexistence of certain cubic graphs with small diameters
• On bipartite graphs of defect 2
• On bipartite graphs of diameter 3 and defect 2
• On Minimal graphs of maximum even girth
• Regular graphs with excess one
• The nonexistence of certain generalized polygons
• Theory and Application of Graphs
• Topology of interconnection networks with given degree and diameter

Cited in

(7)

• On bipartite graphs of defect 2
• Nonexistence of some antipodal distance-regular graphs of diameter four
• On the non-existence of antipodal cages of even girth
• Bipartite biregular Moore graphs
• On bipartite graphs of diameter 3 and defect 2
• Large bipartite Cayley graphs of given degree and diameter
• On bipartite graphs of defect at most 4

Describes a project that uses

Uses Software

• Mathematica

This page was built for publication: Non-existence of bipartite graphs of diameter at least \(4\) and defect \(2\)

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