On new record graphs close to bipartite Moore graphs

DOI10.1007/S00373-022-02500-3zbMATH Open1492.05123arXiv2005.02427OpenAlexW3023977152MaRDI QIDQ2152609FDOQ2152609

Gabriela Araujo, Nacho López

Publication date: 8 July 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The modelling of interconnection networks by graphs motivated the study of several extremal problems that involve well known parameters of a graph (degree, diameter, girth and order) and ask for the optimal value of one of them while holding the other two fixed. Here we focus in {em bipartite Moore graphs/}, that is, bipartite graphs attaining the optimum order, fixed either the degree/diameter or degree/girth. The fact that there are very few bipartite Moore graphs suggests the relaxation of some of the constraints implied by the bipartite Moore bound. First we deal with {em local bipartite Moore graphs}. We find in some cases those local bipartite Moore graphs with local girths as close as possible to the local girths given by a bipartite Moore graph. Second, we construct a family of $(q+2)$-bipartite graphs of order $2(q^2+q+5)$ and diameter $3$, for $q$ a power of prime. These graphs attain the record value for $q=9$ and improve the values for $q=11$ and $q=13$.

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

zbMATH Keywords

bipartite graphgirthbipartite Moore boundlocal girth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Moore graphs and beyond: a survey of the degree/diameter problem
• Dynamic cage survey
• Geometric realisation of the graphs of McKay-Miller-Širáň
• On the existence of radial Moore graphs for every radius and every degree
• Ranking measures for radially Moore graphs
• Radial Moore graphs of radius three
• HSAGA and its application for the construction of near-Moore digraphs
• Families of small regular graphs of girth 5
• On bipartite‐mixed graphs
• Large Graphs with Given Degree and Diameter—Part I
• Large Graphs with Given Degree and Diameter III
• New small regular graphs of girth 5
• Mixed cages: monotonicity, connectivity and upper bounds
• On large bipartite graphs of diameter 3
• Abstract Algebra

Cited In (2)

• Title not available (Why is that?)
• Title not available (Why is that?)

Uses Software

• nauty

   Recommendations

• On Moore bipartite digraphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Bipartite biregular Moore graphs 👍 👎
• A spectral version of the Moore problem for bipartite regular graphs 👍 👎
• A Spectral Moore Bound for Bipartite Semiregular Graphs 👍 👎
• On the structure of digraphs with order close to the Moore bound 👍 👎
• Title not available (Why is that?) 👍 👎
• A revised Moore bound for mixed graphs 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: On new record graphs close to bipartite Moore graphs

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