ARTICLE
TITLE

Small Graphs and Hypergraphs of Given Degree and Girth

SUMMARY

The search for the smallest possible dd-regular graph of girth gg has a long history, and is usually known as the cage problem. This problem has a natural extension to hypergraphs, where we may ask for the smallest number of vertices in a dd-regular, rr-uniform hypergraph of given (Berge) girth gg. We show that these two problems are in fact very closely linked. By extending the ideas of Cayley graphs to the hypergraph context, we find smallest known hypergraphs for various parameter sets. Because of the close link to the cage problem from graph theory, we are able to use these techniques to find new record smallest cubic graphs of girths 23, 24, 28, 29, 30, 31 and 32.

PAGES
pp. P1.57

 Articles related

Jan Goedgebeur    

A snark is a bridgeless cubic graph which is not 3-edge-colourable. The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph.Lukot'ka, Mácajová, Mazák and Škoviera showed in [Electron. J. Comb... see more


Camino Balbuena, Florent Foucaud, Adriana Hansberg    

Locating-dominating sets and identifying codes are two closely related notions in the area of separating systems. Roughly speaking, they consist in a dominating set of a graph such that every vertex is uniquely identified by its neighbourhood within the ... see more


Matthew Jura, Oscar Levin, Tyler Markkanen    

We investigate the apparent difficulty of finding domatic partitions in graphs using tools from computability theory.  We consider nicely presented (i.e., computable) infinite graphs and show that even if the domatic number is known, there might not... see more


Robert R. Lewis    

This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establis... see more


Ralph Keusch, Angelika Steger    

Suppose that two players take turns coloring the vertices of a given graph G with k colors. In each move the current player colors a vertex such that neighboring vertices get different colors. The first player wins this game if and only if at the end, al... see more