On new record graphs close to bipartite Moore graphs

DOI10.1007/S00373-022-02500-3MaRDI QIDQ2152609zbMATH OpenOpenAlexFDO

Authors Gabriela Araujo, Nacho López

Publication date 8 July 2022

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

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)

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

Recommendations

• On Moore bipartite digraphs
• scientific article; zbMATH DE number 5309966
• scientific article; zbMATH DE number 1735799
• 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
• scientific article; zbMATH DE number 3857150
• A revised Moore bound for mixed graphs
• scientific article; zbMATH DE number 1792622

Cites work

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

Cited in

(4)

• scientific article; zbMATH DE number 5309966 (Why is no real title available?)
• Bipartite biregular Moore graphs
• scientific article; zbMATH DE number 3857150 (Why is no real title available?)
• Topology of interconnection networks with given degree and diameter

Describes a project that uses

Uses Software

• nauty

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)