On bipartite graphs of defect at most 4

DOI10.1016/J.DAM.2011.09.002zbMATH Open1241.05022arXiv1010.5651OpenAlexW1968003215MaRDI QIDQ765348FDOQ765348

Ramiro Feria-Purón, Guillermo Pineda-Villavicencio

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We consider the bipartite version of the degree/diameter problem, namely, given natural numbers {Delta} geq 2 and D geq 2, find the maximum number Nb({Delta},D) of vertices in a bipartite graph of maximum degree {Delta} and diameter D. In this context, the Moore bipartite bound Mb({Delta},D) represents an upper bound for Nb({Delta},D). Bipartite graphs of maximum degree {Delta}, diameter D and order Mb({Delta},D), called Moore bipartite graphs, have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree {Delta} geq 2, diameter D geq 2 and order Mb({Delta},D) - epsilon with small epsilon > 0, that is, bipartite ({Delta},D,-epsilon)-graphs. The parameter epsilon is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if {Delta} geq 3 and D geq 3, they may only exist for D = 3. However, when epsilon > 2 bipartite ({Delta},D,-epsilon)-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite $(Delta,d,-4)$-graphs; the complete catalogue of bipartite (3,D,-epsilon)-graphs with D geq 2 and 0 leq epsilon leq 4; the complete catalogue of bipartite ({Delta},D,-epsilon)-graphs with {Delta} geq 2, 5 leq D leq 187 (D /= 6) and 0 leq epsilon leq 4; and a non-existence proof of all bipartite ({Delta},D,-4)-graphs with {Delta} geq 3 and odd D geq 7. Finally, we conjecture that there are no bipartite graphs of defect 4 for {Delta} geq 3 and D geq 5, and comment on some implications of our results for upper bounds of Nb({Delta},D).

Full work available at URL: https://arxiv.org/abs/1010.5651

zbMATH Keywords

defectrepeatMoore bipartite bounddegree/diameter problem for bipartite graphsMoore bipartite graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast generation of regular graphs and construction of cages
• The nonexistence of certain generalized polygons
• Minimal Regular Graphs of Girths Eight and Twelve
• Graphs with even girth and small excess
• On Minimal graphs of maximum even girth
• On bipartite graphs of defect 2
• Non-existence of bipartite graphs of diameter at least \(4\) and defect \(2\)
• On bipartite graphs of diameter 3 and defect 2
• Nonexistence of certain cubic graphs with small diameters
• Cycles in strong oriented graphs

Cited In (2)

• On graphs of defect at most 2
• The degree-diameter problem for outerplanar graphs

Uses Software

• nauty
• GENREG

This page was built for publication: On bipartite graphs of defect at most 4

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