Graphs with girth at least 5 with orders between 20 and 32

2017/08/22 by Alice Miller, Miller, Alice, Michael Codish +1
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1708.06576

openalex publication_date 2017/08/22 · arxiv created 2017/08/23 · arxiv updated 2017/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove properties of extremal graphs of girth 5 and order 20 <=v <= 32. In each case we identify the possible minimum and maximum degrees, and in some cases prove the existence of (non-trivial) embedded stars. These proofs allow for tractable search for and identification of all non isomorphic cases.

Related

• Sizes of the extremal girth 5 graphs of orders from 40 to 49
• Graphs with large girth and nonnegative curvature dimension condition
• Graphs of large girth
• New families of small regular graphs of girth 5
• On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration