On bipartite graphs of defect at most 4

DOI10.1016/J.DAM.2011.09.002MaRDI QIDQ765348zbMATH OpenOpenAlexFDO

Authors Guillermo Pineda-Villavicencio, Ramiro Feria-Purón

Publication date 19 March 2012

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

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)

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).

Recommendations

• Non-existence of bipartite graphs of diameter at least \(4\) and defect \(2\)
• On bipartite graphs of diameter 3 and defect 2
• On bipartite graphs of defect 2
• On graphs of defect at most 2
• Nonexistence of graphs with cyclic defect

Cites work

• scientific article; zbMATH DE number 4059445 (Why is no real title available?)
• scientific article; zbMATH DE number 2010366 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Cycles in strong oriented graphs
• Fast generation of regular graphs and construction of cages
• Graphs with even girth and small excess
• Minimal Regular Graphs of Girths Eight and Twelve
• Non-existence of bipartite graphs of diameter at least \(4\) and defect \(2\)
• Nonexistence of certain cubic graphs with small diameters
• On Minimal graphs of maximum even girth
• On bipartite graphs of defect 2
• On bipartite graphs of diameter 3 and defect 2
• The nonexistence of certain generalized polygons

Cited in

(6)

• On graphs of defect at most 2
• On bipartite graphs of defect 2
• Complete catalogue of graphs of maximum degree 3 and defect at most 4
• On bipartite graphs of diameter 3 and defect 2
• The degree-diameter problem for outerplanar graphs
• Non-existence of bipartite graphs of diameter at least \(4\) and defect \(2\)

Describes a project that uses

Uses Software

• GENREG
• nauty

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)