Abstract: The first known families of cages arised from the incidence graphs of generalized polygons of order , a prime power. In particular, --cages have been obtained from the projective planes of order . Morever, infinite families of small regular graphs of girth 5 have been constructed performing algebraic operations on . In this paper, we introduce some combinatorial operations to construct new infinite families of small regular graphs of girth 7 from the --cages arising from the generalized quadrangles of order , a prime power.
Summary: In this paper, we construct new infinite families of regular graphs of girth 7 of smallest order known so far. Our constructions are based on combinatorial and geometric properties of \((q+1,8)\)-cages, for \(q\) a prime power. We remove vertices from such cages and add matchings among the vertices of minimum degree to achieve regularity in the new graphs. We obtain \((q+1)\)-regular graphs of girth 7 and order \(2q^3+q^2+2q\) for each even prime power \(q \geq 4\), and of order \(2q^3+2q^2-q+1\) for each odd prime power \(q\geqslant 5\).
Recommendations
Cites work
- A construction of small \((q-1)\)-regular graphs of girth 8
- A construction of small regular bipartite graphs of girth 8
- A family of regular graphs of girth 5
- A linear interpretation of the flag geometries of Chevalley groups
- A simple method for constructing small cubic graphs of girths 14, 15, and 16
- Affine representations of generalized quadrangles
- Cages—a survey
- Constructions for cubic graphs with large girth
- Constructions of small regular bipartite graphs of girth 6
- Dynamic cage survey
- Explicit construction of graphs with an arbitrary large girth and of large size
- Families of small regular graphs of girth 5
- Fast generation of regular graphs and construction of cages
- Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages
- Graph theory
- scientific article; zbMATH DE number 3877205 (Why is no real title available?)
- scientific article; zbMATH DE number 1219619 (Why is no real title available?)
- scientific article; zbMATH DE number 979131 (Why is no real title available?)
- scientific article; zbMATH DE number 3445271 (Why is no real title available?)
- scientific article; zbMATH DE number 3432305 (Why is no real title available?)
- scientific article; zbMATH DE number 227006 (Why is no real title available?)
- scientific article; zbMATH DE number 3256347 (Why is no real title available?)
- scientific article; zbMATH DE number 3189017 (Why is no real title available?)
- scientific article; zbMATH DE number 3046496 (Why is no real title available?)
- Incidence Matrices of Projective Planes and of Some Regular Bipartite Graphs of Girth 6 with Few Vertices
- Minimal Regular Graphs of Girths Eight and Twelve
- New upper bounds on the order of cages
- On (minimal) regular graphs of girth \(6\)
- On geometric constructions of \((k,g)\)-graphs
- On the connectivity of cages with girth five, six and eight
- Sur la trialité et certains groupes qui s'en déduisent
- The 10-cages and derived configurations
- The nonexistence of certain generalized polygons
- The Smallest Cubic Graphs of Girth Nine
- The smallest graph of girth 6 and valency 7
Cited in
(9)- A construction of small \((q-1)\)-regular graphs of girth 8
- New small regular graphs of girth 5
- Recursive constructions of small regular graphs of given degree and girth
- scientific article; zbMATH DE number 1439410 (Why is no real title available?)
- On the automorphisms of a family of small q-regular graphs of girth 8
- An alternate description of a \((q + 1, 8)\)-cage
- Geometric constructions of small regular graphs with girth 7
- Contributions on the cage and diameter problems and beyond
- Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages
This page was built for publication: Small regular graphs of girth 7
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2517652)
