In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph and contains information about how the graph is connected. It is denoted by .
In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.
In the mathematical field of graph theory, the odd graphsOn are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970).
In the mathematical field of graph theory, the Harries graph or Harries (3-10)-cage is a 3-regular, undirected graph with 70 vertices and 105 edges.
In the mathematical field of graph theory, the Harries–Wong graph is a 3-regular undirected graph with 70 vertices and 105 edges.
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges.
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.
In the mathematical field of graph theory, the Folkman graph, named after Jon Folkman, is a bipartite 4-regular graph with 20 vertices and 40 edges.
In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban.
In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.
In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997.
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte.
The 110-vertex Iofinova-Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.
In the mathematical field of graph theory, the Robertson–Wegner graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Neil Robertson and G. Wegner.
In the mathematical field of graph theory, the Wong graph is a 5-regular undirected graph with 30 vertices and 75 edges. It is one of the four (5,5)-cage graphs, the others being the Foster cage, the Meringer graph, and the Robertson–Wegner graph.
